Roger has a list of $N$ positive integers $A_1,A_2,\dots ,A_N$. However, his list is not yet finalized. Some of these numbers are wildcards which will be represented as zeroes in the list. Roger will try to assign the wildcards a value so that

• The list $A$ is sorted from least to greatest
• All wildcards have the same value, which is a positive integer

Help Roger find out if this is possible. Output YES if he can assign the wildcards a value so that $A$ is sorted and NO otherwise.

Constraints

$0\le A_i\le 1000000$ for all $1\le i\le N$.
If $A_i=0$, then it is a wildcard, otherwise $1\le A_i\le 1000000$.

Subtask 1 [30%]

$1\le N\le 100$

Subtask 2 [30%]

$1\le N\le 1000$

Subtask 3 [40%]

$1\le N\le 200000$

Input Specification

The first line contains a single integer $N$.
The next line contains $N$ space-separated integers, $A_1,A_2,\dots ,A_N$.

Output Specification

Output a single string: YES if it is possible and NO otherwise.

Sample Input 1

6
0 0 1 5 5 5

Sample Output 1

YES

Explanation for Sample Output 1

The first two elements are wildcards. Setting them to $1$ gives a sorted list.

Sample Input 2

6
1 5 5 5 5 1

Sample Output 2

NO

Explanation for Sample 2

There are no wildcards, so Roger cannot do anything. $A$ is not sorted so the answer is no.

Sample Input 3

6
1 0 2 0 3 0

Sample Output 3

NO