Codeforces и Polygon могут быть недоступны в период с 23 мая, 7:00 (МСК) по 23 мая, 11:00 (МСК) в связи с проведением технических работ. ×
C. Уничтожение элементов
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дан массив $$$a$$$ длины $$$n$$$, который изначально является перестановкой чисел от $$$1$$$ до $$$n$$$. За одну операцию, вы можете выбрать индекс $$$i$$$ ($$$1 \leq i < n$$$), такой что $$$a_i < a_{i + 1}$$$, и удалить либо $$$a_i$$$ или $$$a_{i + 1}$$$ из массива (после удаления оставшиеся части воссоединяются).

Например, если у вас есть массив $$$[1, 3, 2]$$$, вы можете выбрать $$$i = 1$$$ (так как $$$a_1 = 1 < a_2 = 3$$$), и либо удалить $$$a_1$$$, что даст новый массив $$$[3, 2]$$$, или удалить $$$a_2$$$, что даст новый массив $$$[1, 2]$$$.

Можно ли сделать длину этого массива равной $$$1$$$ с помощью этих операций?

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

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

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

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1$$$, $$$a_2$$$, ..., $$$a_n$$$ ($$$1 \leq a_i \leq n$$$, $$$a_i$$$ попарно различны) — элементы массива.

Гарантируется, что сумма $$$n$$$ по всем тестовым случаям не превышает $$$3 \cdot 10^5$$$.

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

Для каждого набора входных данных выведите в отдельной строке слово "YES", если возможно свести массив к одному элементу с помощью вышеупомянутой операции, или "NO", если это невозможно сделать.

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

Для первых двух и четвертого наборов входных данных мы можем действовать следующим образом (выделенные жирным шрифтом элементы  — это пара, выбранная для этой операции):

$$$[\text{1}, \textbf{2}, \textbf{3}] \rightarrow [\textbf{1}, \textbf{2}] \rightarrow [\text{1}]$$$

$$$[\text{3}, \textbf{1}, \textbf{2}, \text{4}] \rightarrow [\text{3}, \textbf{1}, \textbf{4}] \rightarrow [\textbf{3}, \textbf{4}] \rightarrow [\text{4}]$$$

$$$[\textbf{2}, \textbf{4}, \text{6}, \text{1}, \text{3}, \text{5}] \rightarrow [\textbf{4}, \textbf{6}, \text{1}, \text{3}, \text{5}] \rightarrow [\text{4}, \text{1}, \textbf{3}, \textbf{5}] \rightarrow [\text{4}, \textbf{1}, \textbf{5}] \rightarrow [\textbf{4}, \textbf{5}] \rightarrow [\text{4}]$$$