LRU Puzzle

AtCoder

IDcodefestival_2016_qualA_e

Time2000ms

Memory256MB

Difficulty—

There are $N$ arrays. The length of each array is $M$ and initially each array contains integers $(1，2，...，M)$ in this order. Mr. Takahashi has decided to perform $Q$ operations on those $N$ arrays. For the $i$\-th ($1≤i≤Q$) time, he performs the following operation. * Choose an arbitrary array from the $N$ arrays and move the integer $a_i$ ($1≤a_i≤M$) to the front of that array. For example, after performing the operation on $a_i=2$ and the array $(5，4，3，2，1)$, this array becomes $(2，5，4，3，1)$. Mr. Takahashi wants to make $N$ arrays exactly the same after performing the $Q$ operations. Determine if it is possible or not. ## Constraints * $2≤N≤10^5$ * $2≤M≤10^5$ * $1≤Q≤10^5$ * $1≤a_i≤M$ ## Input The input is given from Standard Input in the following format: $N$ $M$ $Q$ $a_1$ $a_2$ $...$ $a_Q$ [samples]

Samples

Input #1

2 2
3
2 1 2

Output #1

Yes

You can perform the operations as follows.
![image](/img/other/code_festival_2016_quala/gbanjthabot/E_0.png)

Input #2

3 2
3
2 1 2

Output #2

No

Input #3

2 3
3
3 2 1

Output #3

Yes

You can perform the operations as follows.
![image](/img/other/code_festival_2016_quala/gbanjthabot/E_2.png)

Input #4

3 3
6
1 2 2 3 3 3

Output #4

No

API Response (JSON)

{
  "problem": {
    "name": "LRU Puzzle",
    "description": {
      "content": "There are $N$ arrays. The length of each array is $M$ and initially each array contains integers $(1，2，...，M)$ in this order. Mr. Takahashi has decided to perform $Q$ operations on those $N$ arrays. F",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "codefestival_2016_qualA_e"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "There are $N$ arrays. The length of each array is $M$ and initially each array contains integers $(1，2，...，M)$ in this order.\nMr. Takahashi has decided to perform $Q$ operations on those $N$ arrays. F...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments