Luka often travels to programming camps. Fees last n days. Luka records the number of tasks solved on each day of the camp. Luka considers the camp "effective" if there is only one continuous non-zero span of days (from l to r) when the following conditions were met for the number of solved problems:
1 <= l <= r <= n;al = al+1 = al+2 =…=ar;l = 1 or al-1 > al;r = n or ar < ar+1;
Examples
Let the A array store information about the solution of problems for each day of training, then:
1) array A = [5, 3, 3, 2, 3, 3, 4] describes "efficient", according to Luke, fees (interval of 1 day l = r = 4 satisfies the condition);
2) array A = [2, 2, 2, 3, 4, 4, 5, 6, 7, 7, 8] also describes «efficient " charges (interval l = 1, r = 3 satisfies the condition);
3) array A = [1, 2, 3, 4, 3, 2, 1] describes not "efficient" fees (there are two intervals that satisfy the condition l = r = 1 and l = r = 7).
Luca just got back from another programming camp and told you how many problems he solved every day. Determine if the fees returned by Luca are "effective" in his opinion.
Input
The first line contains a single integer
n (1 <=
n <= 2·10
5) &mdash ; array length. Second line
n integers
ai (1 <=
ai <= 10
9) — the number of problems solved by Luca on the
i-th day .
Imprint
Print
YES if Luka's collection was effective, and
NO otherwise.
Examples
| # |
Input |
Output |
| 1 |
7
5 3 3 2 3 3 4 |
YES |
| 2 |
11
2 2 2 3 4 4 5 6 7 7 8
YES |
|
| 3 |
7
1 2 3 4 3 2 1
NO |
|