B. Оптимальное уменьшение
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У вас есть массив $$$a$$$ из $$$n$$$ положительных чисел.

Вы можете выполнять следующую операцию:

  • выберите два индекса $$$l$$$ и $$$r$$$ ($$$1 \leq l \leq r \leq n$$$), затем
  • уменьшите элементы $$$a_l, a_{l + 1}, \dots, a_r$$$ на $$$1$$$ каждый.

Пусть $$$f(a)$$$ равно минимальному числу операций, необходимому, чтобы превратить массив $$$a$$$ в массив из $$$n$$$ нулей.

Определите, верно ли, что для всех перестановок$$$^\dagger$$$ $$$b$$$ массива $$$a$$$ выполняется $$$f(a) \leq f(b)$$$.

$$$^\dagger$$$ Массив $$$b$$$ является перестановкой массива $$$a$$$, если $$$b$$$ состоит из элементов массива $$$a$$$ в произвольном порядке. Например, $$$[4,2,3,4]$$$ является перестановкой $$$[3,2,4,4]$$$, а $$$[1,2,2]$$$ не является перестановкой $$$[1,2,3]$$$.

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

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

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

Вторая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — описание массива $$$a$$$.

Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$10^5$$$.

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

Для каждого набора входных данных выведите «YES» (без кавычек), если для всех перестановок $$$b$$$ массива $$$a$$$ выполняется $$$f(a) \leq f(b)$$$, и «NO» (без кавычек) иначе.

Вы можете выводить буквы в «YES» и «NO» в любом регистре (например, строки «yEs», «yes» и «Yes» будут приняты как положительный ответ).

Пример
Входные данные
3
4
2 3 5 4
3
1 2 3
4
3 1 3 2
Выходные данные
YES
YES
NO
Примечание

В первом примере можно превратить все элементы в $$$0$$$ за $$$5$$$ операций. Можно показать, что не существует перестановки массива $$$[2, 3, 5, 4]$$$ такой, что все ее элементы можно превратить в $$$0$$$ меньше чем за $$$5$$$.

В третьем примере необходимо $$$5$$$ операций, чтобы превратить все элементы в $$$0$$$, а перестановка, равная $$$[2, 3, 3, 1]$$$, требует только $$$3$$$ операции.