D. Долины с трудностями
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дан массив $$$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$$$.

Входные данные

Первая строка содержит одно целое число $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — количество наборов входных данных.

Первая строка каждого набора содержит одно целое число $$$n$$$ ($$$1 \leq n \leq 2\cdot10^5$$$) — длину массива.

Вторая строка каждого набора содержит $$$n$$$ целых чисел $$$a_i$$$ ($$$1 \leq a_i \leq 10^9$$$) — элементы массива.

Гарантируется, что сумма $$$n$$$ по всем наборам не превышает $$$2\cdot10^5$$$.

Выходные данные

Для каждого набора выведите «YES» (без кавычек), если массив является долиной, и «NO» (без кавычек) в противном случае.

Вы можете вывести ответ в любом случае (например, строки «YEs», «Yes», «Yes» и «YES» будут распознаны как положительный ответ).

Пример
Входные данные
6
7
3 2 2 1 2 2 3
11
1 1 1 2 3 3 4 5 6 6 6
7
1 2 3 4 3 2 1
7
9 7 4 6 9 9 10
1
1000000000
8
9 4 4 5 9 4 9 10
Выходные данные
YES
YES
NO
YES
YES
NO
Примечание

Первые три набора входных данных примера разобраны в условии.