Simple Problem

Time limit1sMemory limit1024 MB

Summary

Given p and a sequence b, decide whether some permutation of 1 to N makes the maximum residue-class count over each prefix equal b_i.

Level: Medium6 of 10
Topics: Greedy, Math, Implementation
Solved: No attempts yet

Problem

After leaving PULSE and entering graduate school, Sanjini is fishing at Taejongdae on a holiday, hoping to catch a big one. Hours pass with no bite. Sleepy from holding the rod for so long, Sanjini starts thinking about a simple sequence.

For a permutation $a$ of length $N$ , define $S$ and a sequence $b$ as follows.

$S_{i,j}$ ( $1 \leq i \leq N$ ) is the number of elements among $a_1, a_2, \ldots, a_i$ whose remainder modulo $p$ is $j$ ( $0 \leq j < p$ ).
$b_i$ ( $1 \leq i \leq N$ ) is the maximum of $S_{i,0}, S_{i,1}, \ldots, S_{i,p-1}$ .

Sanjini thinks a little longer and wonders whether a permutation $a$ exists for a given $p$ and sequence $b$ . Determine whether a permutation $a$ that satisfies the conditions exists.

Input

The first line contains the length $N$ of sequence $b$ and the integer $p$ , separated by a space. $(1 \leq N, p \leq 5 \times 10^5)$

The second line contains the elements $b_1, b_2, \ldots, b_N$ of sequence $b$ in order, separated by spaces. $(1 \leq b_i \leq N)$

Output

If a permutation $a$ that satisfies the conditions exists, print YES. Otherwise, print NO.

Hint

A permutation of length $N$ is a finite sequence in which each integer from 1 to $N$ is used exactly once. For example, $\{1, 2, 4, 3\}$ is a permutation, but $\{1, 4, 2\}$ and $\{1, 3, 3, 2\}$ are not.

Examples4

Example 1
Input
```
3 1
1 2 3
```
Expected output
```
YES
```
Example 2
Input
```
5 2
1 2 2 2 2
```
Expected output
```
NO
```
Example 3
Input
```
3 6
1 1 1
```
Expected output
```
YES
```
Example 4
Input
```
7 2
1 2 3 2 3 3 4
```
Expected output
```
NO
```