## DMOPC '18 Contest 1 P1 - Sorting

View as PDF

Points: 5 (partial)
Time limit: 2.0s
Java 2.5s
Python 2.5s
Memory limit: 64M

Author:
Problem type

Roger has a list of positive integers . 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 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 is sorted and NO otherwise.

#### Constraints

for all .
If , then it is a wildcard, otherwise .

#### Input Specification

The first line contains a single integer .
The next line contains space-separated integers, .

#### 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 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. is not sorted so the answer is no.

#### Sample Input 3

6
1 0 2 0 3 0

#### Sample Output 3

NO