D. Рэй Тейлор и деревья (простая версия)
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Это простая версия задачи. Единственное отличие между простой и сложной версиями заключается в том, что сложная версия просит вас построить пример удовлетворяющего дерева.

Как маг Земли, Рэй овладела заклинанием роста деревьев! Но Манария хвастается, что она может вырастить более впечатляющий вид деревьев. Рэй помнит, что самый редкий тип дерева можно вырастить, используя формулу, представленную определенной перестановкой — пожалуйста, помогите ей построить его!

Вам дана перестановка$$$^{\text{∗}}$$$ $$$p$$$ длины $$$n$$$.

Определите, существует ли неориентированное дерево с $$$n$$$ вершинами, пронумерованными $$$1, 2, \dots, n$$$, удовлетворяющее следующему условию:

  • Пусть $$$u$$$ и $$$v$$$ ($$$1\leq {\color{red}{u \lt v}} \leq n$$$) будут любыми двумя вершинами, соединенными ребром. Тогда $$$u$$$ появляется перед $$$v$$$ в $$$p$$$.

$$$^{\text{∗}}$$$Перестановка длины $$$n$$$ — это массив, который содержит каждое целое число от $$$1$$$ до $$$n$$$ ровно один раз, в любом порядке.

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

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

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

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел, $$$p_1, p_2, \dots, p_n$$$ ($$$1\leq p_i\leq n$$$). Гарантируется, что все $$$p_i$$$ различны.

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

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

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

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

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

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

  • $$$\{3, 1\}$$$,
  • $$$\{4, 1\}$$$,
  • $$$\{6, 5\}$$$,
  • $$$\{6, 2\}$$$,
  • $$$\{6, 1\}$$$.

Тогда у нас есть:

  • $$$1 \lt 3$$$, и $$$1$$$ появляется перед $$$3$$$ в $$$p$$$,
  • $$$1 \lt 4$$$, и $$$1$$$ появляется перед $$$4$$$ в $$$p$$$,
  • $$$5 \lt 6$$$, и $$$5$$$ появляется перед $$$6$$$ в $$$p$$$,
  • $$$2 \lt 6$$$, и $$$2$$$ появляется перед $$$6$$$ в $$$p$$$,
  • $$$1 \lt 6$$$, и $$$1$$$ появляется перед $$$6$$$ в $$$p$$$.

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