Вам дан массив \(a[0 \dots n-1]\) из \(n\) целых чисел. Этот массив называется «долиной», если существует ровно один подмассив \(a[l \dots r]\) такой, что:
- \(0 \le l \le r \le n-1\),
- \(a_l = a_{l+1} = a_{l+2} = \dots = a_r\),
- \(l = 0\) или \(a_{l-1} > a_{l}\),
- \(r = n-1\) или \(a_r < a_{r+1}\).
Вот три примера:
На первом изображении показан массив [\(3, 2, 2, 1, 2, 2, 3\)], он является долиной, потому что только подмассив с индексами \(l=r=3\) удовлетворяет условию.
На втором изображении показан массив [\(1, 1, 1, 2, 3, 3, 4, 5, 6, 6, 6\)], он является долиной, потому что только подмассив с индексами \(l=0, r=2\) удовлетворяет условию.
На третьем изображении показан массив [\(1, 2, 3, 4, 3, 2, 1\)], он не является долиной, потому что два подмассива \(l=r=0\) и \(l=r=6\) удовлетворяют условию.
Определите, является ли данный массив долиной или нет.
Обратите внимание, что мы считаем массив индексированным с \(0\).
Выходные данные
Для каждого набора выведите «YES» (без кавычек), если массив является долиной, и «NO» (без кавычек) в противном случае.
Вы можете вывести ответ в любом случае (например, строки «YEs», «Yes», «Yes» и «YES» будут распознаны как положительный ответ).