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
~0\le A_i\le 1\,000\,000~ for all ~1\le i\le N~
If ~A_i=0~, then it is a wildcard, otherwise ~1\le A_i\le 1\,000\,000~.
The first line contains a single integer ~N~.
The next line contains ~N~ space-separated integers, ~A_1, A_2, \dots, A_N~.
Output a single string:
YES if it is possible and
Subtask 1 [30%]
~1\le N\le 100~
Subtask 2 [30%]
~1\le N\le 1\,000~
Subtask 3 [40%]
~1\le N\le 200\,000~
Sample Input 1
6 0 0 1 5 5 5
Sample Output 1
Explanation for Sample Input 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
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