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 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~.

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~

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