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

Есть $$$n+2$$$ позиций, пронумерованных от $$$0$$$ до $$$n+1$$$. Изначально на позиции $$$i$$$ находится элемент веса $$$w_i$$$ для каждого $$$1\le i\le n$$$, а позиции $$$0$$$ и $$$n+1$$$ пусты.

Вы выбираете целое число $$$k$$$. Затем все элементы одновременно перемещаются ровно один раз:

  • Если $$$w_i \lt k$$$, элемент на позиции $$$i$$$ перемещается на позицию $$$i-1$$$;
  • Если $$$w_i \gt k$$$, элемент на позиции $$$i$$$ перемещается на позицию $$$i+1$$$;
  • Если $$$w_i=k$$$, весь процесс перемещения немедленно завершается неудачей.

Целое число $$$k$$$ называется идеальным, если перемещение не завершается неудачей и после его окончания каждая позиция от $$$1$$$ до $$$n$$$ содержит ровно один элемент.

Определите, существует ли идеальное целое число $$$k$$$.

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

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

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$1\le n\le 100$$$).

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$w_1,w_2,\ldots,w_n$$$ ($$$1\le w_i\le 10^9$$$).

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

Для каждого набора входных данных выведите «YES», если идеальное целое число $$$k$$$ существует, и «NO» в противном случае.

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

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

В первом наборе входных данных единственный элемент либо покидает позицию $$$1$$$, либо имеет вес, равный $$$k$$$, поэтому подходящего целого числа не существует.

Во втором наборе входных данных выберите $$$k=2$$$. Элемент веса $$$3$$$ движется вправо, а элемент веса $$$1$$$ — влево, и на каждой позиции оказывается по одному элементу.

В третьем наборе входных данных для того, чтобы обе позиции были заняты, потребовалось бы $$$1 \lt k \lt 2$$$, что невозможно для целого $$$k$$$.

В четвёртом наборе входных данных подходит $$$k=5$$$: элементы на позициях $$$1$$$ и $$$3$$$ движутся вправо, а элементы на позициях $$$2$$$ и $$$4$$$ — влево. После завершения процесса каждая позиция от $$$1$$$ до $$$4$$$ содержит ровно один элемент.

В пятом наборе входных данных элемент на позиции $$$2$$$ должен двигаться влево, что требует $$$k \gt 8$$$, а элемент на позиции $$$3$$$ должен двигаться вправо, что требует $$$k \lt 7$$$. Эти требования несовместимы.

В шестом наборе входных данных выберите $$$k=4$$$. Все элементы на нечётных позициях движутся вправо, а все элементы на чётных позициях — влево, поэтому после этого каждая позиция от $$$1$$$ до $$$6$$$ содержит по одному элементу.