Олимпиадный тренинг

Задача . Эффективные сборы


Задача

Темы: "Два указателя"

Лука часто ездит на сборы по программированию. Сборы длятся n дней. Лука фиксирует количество решенных задач в каждый день сборов. Лука считает сборы «эффективными», если только один непрерывный не нулевой промежуток дней (от l до r), когда выполнялись следующие условия по числу решенных задач:

  • 1 <= l <= r <= n;
  • al = al+1 = al+2 =…=ar;
  • l = 1 или al-1 > al;
  • r = n или ar < ar+1;
Примеры 

Пусть массив хранит информацию о решении задач за каждый день сборов, тогда:

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·105) — длину массива. Вторая строка n целых чисел ai (1 <= a<= 109) — количество решенных Лукой задач в 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



time 1000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
С++ Mingw-w643
Python3
Комментарий учителя