A. Косвенная сортировка
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дана перестановка $$$a_1, a_2, \ldots, a_n$$$ размера $$$n$$$, где каждое целое число от $$$1$$$ до $$$n$$$ встречается ровно один раз.

Вы можете выполнить следующую операцию любое количество раз (возможно, ноль):

  • Выбрать любые три индекса $$$i, j, k$$$ ($$$1 \le i < j < k \le n$$$).
  • Если $$$a_i > a_k$$$, заменить $$$a_i$$$ на $$$a_i + a_j$$$. В противном случае поменять местами $$$a_j$$$ и $$$a_k$$$.

Определите, можно ли отсортировать массив $$$a$$$ в порядке неубывания.

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

Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит единственное целое число $$$t$$$ ($$$1 \le t \le 5000$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

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

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1,a_2,\dots,a_n$$$ ($$$1 \le a_i \le n$$$, $$$a_i \neq a_j$$$, если $$$i \neq j$$$) — элементы массива $$$a$$$.

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

Для каждого набора входных данных выведите «Yes» (без кавычек), если массив можно отсортировать в неубывающем порядке, и «No» (без кавычек) в противном случае.

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

Пример
Входные данные
7
3
1 2 3
3
1 3 2
7
5 3 4 7 6 2 1
7
7 6 5 4 3 2 1
5
2 1 4 5 3
5
2 1 3 4 5
7
1 2 6 7 4 3 5
Выходные данные
Yes
Yes
No
No
No
No
Yes
Примечание

В первом наборе входных данных массив $$$[1,2,3]$$$ уже отсортирован в порядке неубывания.

Во втором наборе входных данных мы можем выбрать $$$i = 1,j = 2,k = 3$$$. Так как $$$a_1 \le a_3$$$, поменяем местами $$$a_2$$$ и $$$a_3$$$, тогда массив станет $$$[1,2,3]$$$, который отсортирован в порядке неубывания.

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

  • Выберем $$$i = 5,j = 6,k = 7$$$. Поскольку $$$a_5 \le a_7$$$, поменяем местами $$$a_6$$$ и $$$a_7$$$, тогда массив станет $$$[1,2,6,7,4,5,3]$$$.
  • Выберем $$$i = 5,j = 6,k = 7$$$. Поскольку $$$a_5 > a_7$$$, заменим $$$a_5$$$ на $$$a_5+a_6=9$$$, тогда массив станет $$$[1,2,6,7,9,5,3]$$$.
  • Выберем $$$i = 2,j = 5,k = 7$$$. Поскольку $$$a_2 \le a_7$$$, поменяем местами $$$a_5$$$ и $$$a_7$$$, тогда массив станет $$$[1,2,6,7,3,5,9]$$$.
  • Выберем $$$i = 2,j = 4,k = 6$$$. Поскольку $$$a_2 \le a_6$$$, поменяем местами $$$a_4$$$ и $$$a_6$$$, тогда массив станет $$$[1,2,6,5,3,7,9]$$$.
  • Выберем $$$i = 1,j = 3,k = 5$$$. Поскольку $$$a_1 \le a_5$$$, поменяем местами $$$a_3$$$ и $$$a_5$$$, тогда массив станет $$$[1,2,3,5,6,7,9]$$$, который отсортирован в порядке неубывания.

В третьем, четвертом, пятом и шестом наборах входных данных можно показать, что массив нельзя отсортировать в порядке неубывания.