D. Омкар и медианы
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

О-о-о! Рэй снова потерял свой массив! Однако Омкар может помочь, потому что он думает, что нашел OmkArray массива Рэя. OmkArray массива $$$a$$$ с элементами $$$a_1, a_2, \ldots, a_{2k-1}$$$ — это массив $$$b$$$ с элементами $$$b_1, b_2, \ldots, b_{k}$$$ такой, что $$$b_i$$$ равен медиане $$$a_1, a_2, \ldots, a_{2i-1}$$$ для всех $$$i$$$. Омкар нашел массив $$$b$$$ размера $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$, $$$-10^9 \leq b_i \leq 10^9$$$). Для этого массива $$$b$$$, Рэй хочет проверить утверждение Омкара и узнать, действительно ли $$$b$$$ является OmkArray некоторого массива $$$a$$$. Можете ли вы помочь Рэю?

Медиана набора чисел $$$a_1, a_2, \ldots, a_{2i-1}$$$ — это число $$$c_{i}$$$, где $$$c_{1}, c_{2}, \ldots, c_{2i-1}$$$ представляют собой $$$a_1, a_2, \ldots, a_{2i-1}$$$, отсортированные в неубывающем порядке.

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

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

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

Вторая строка содержит $$$n$$$ целых чисел $$$b_1, b_2, \ldots, b_n$$$ ($$$-10^9 \leq b_i \leq 10^9$$$) — элементы $$$b$$$.

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

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

Для каждого набора входных данных выведите одну строку, содержащую YES, если существует массив $$$a$$$ такой, что $$$b_i$$$ является медианой $$$a_1, a_2, \dots, a_{2i-1}$$$ для всех $$$i$$$, и NO в противном случае. Регистр букв в YES и NO не имеет значения (поэтому yEs и No также будут приняты).

Примеры
Входные данные
5
4
6 2 1 3
1
4
5
4 -8 5 6 -7
2
3 3
4
2 1 2 3
Выходные данные
NO
YES
NO
YES
YES
Входные данные
5
8
-8 2 -6 -5 -4 3 3 2
7
1 1 3 1 0 -2 -1
7
6 12 8 6 2 6 10
6
5 1 2 3 6 7
5
1 3 4 3 0
Выходные данные
NO
YES
NO
NO
NO
Примечание

Во втором наборе входных данных первого примера массив $$$[4]$$$ даст OmkArray $$$[4]$$$, так как медиана первого элемента равна $$$4$$$.

В четвертом наборе входных данных первого примера массив $$$[3, 2, 5]$$$ даст OmkArray $$$[3, 3]$$$, так как медиана $$$3$$$ равна $$$3$$$, а медиана $$$2, 3, 5$$$ равна $$$3$$$.

В пятом наборе входных данных первого примера массив $$$[2, 1, 0, 3, 4, 4, 3]$$$ даст OmkArray $$$[2, 1, 2, 3]$$$, так как

  • медиана $$$2$$$ равна $$$2$$$
  • медиана $$$0, 1, 2$$$ равна $$$1$$$
  • медиана $$$0, 1, 2, 3, 4$$$ равна $$$2$$$
  • и медиана $$$0, 1, 2, 3, 3, 4, 4$$$ равна $$$3$$$.

Во втором наборе входных данных второй выборки массив $$$[1, 0, 4, 3, 5, -2, -2, -2, -4, -3, -4, -1, 5]$$$ даст OmkArray $$$[1, 1, 3, 1, 0, -2, -1]$$$, как

  • медиана $$$1$$$ равна $$$1$$$
  • медиана из $$$0, 1, 4$$$ равна $$$1$$$
  • медиана из $$$0, 1, 3, 4, 5$$$ равна $$$3$$$
  • медиана $$$-2, -1, 0, 1, 3, 4, 5$$$ равна $$$1$$$
  • медиана $$$-4, -2, -2, -2, 0, 1, 3, 4, 5$$$ равна $$$0$$$
  • медиана $$$-4, -4, -3, -2, -2, -2, 0, 1, 3, 4, 5$$$ равна $$$-2$$$
  • и медиана $$$-4, -4, -3, -2, -2, -2, -1, 0, 1, 3, 4, 5, 5$$$ равна $$$-1$$$

Для всех случаев, когда ответ NO, можно доказать, что невозможно найти массив $$$a$$$ такой, что $$$b$$$ является Omkarray $$$a$$$.