Лука часто ездит на сборы по программированию. Сборы длятся n дней. Лука фиксирует количество решенных задач в каждый день сборов. Лука считает сборы «эффективными», если только один непрерывный не нулевой промежуток дней (от l до r), когда выполнялись следующие условия по числу решенных задач:
1 <= l <= r <= n;al = al+1 = al+2 =…=ar;l = 1 или al-1 > al;r = n или ar < ar+1;
Примеры
Пусть массив A хранит информацию о решении задач за каждый день сборов, тогда:
1) массив A = [5, 3, 3, 2, 3, 3, 4] описывает «эффективные», по мнению Луки, сборы (промежуток в 1 день l = r = 4 удовлетворяет условию);
2) массив А = [2, 2, 2, 3, 4, 4, 5, 6, 7, 7, 8] также описывает «эффективные» сборы (промежут l = 1, r = 3 удовлетворяет условию);
3) массив А = [1, 2, 3, 4, 3, 2, 1] описывает не «эффективные» сборы (есть два промежутка удовлетворяющих условию l = r = 1 и l = r = 7).
Лука только что вернулся с очередных сборов по программированию и рассказал вам сколько задач ежедневно он решал. Определите, являются ли сборы, с которых вернулся Лука «эффективными» по его же мнению.
Входные данные
Первая строка содержит одно целое число
n (1 <=
n <= 2·10
5) — длину массива. Вторая строка
n целых чисел
ai (1 <=
ai <= 10
9) — количество решенных Лукой задач в
i-й день .
Выходные данные
Выведите
YES, если сборы Луки оказались эффективными, и
NO в противном случае.
Примеры
| № |
Входные данные |
Выходные данные |
| 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 |