C. Самый левый меньший
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Рассмотрим массив $$$a_1, \ldots, a_n$$$. Изначально $$$a_i = 0$$$ для каждого $$$i$$$.

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

  • Вы выбираете целое число $$$x$$$, большее чем $$$\min(a)$$$.
  • Затем $$$i$$$ определяется как минимальный индекс, такой что $$$a_i \lt x$$$. Другими словами, $$$i$$$ — это уникальное целое число от $$$1$$$ до $$$n$$$, такое что $$$a_i \lt x$$$ и $$$a_j \geq x$$$ для каждого $$$1 \leq j \leq i-1$$$.
  • В конце $$$a_i$$$ увеличивается на $$$x$$$.

Например, если $$$a = [6, 8, 2, 1]$$$ и вы выбираете $$$x = 6$$$, тогда $$$i$$$ будет равен $$$3$$$ (так как $$$a_1 \geq 6$$$, $$$a_2 \geq 6$$$ и $$$a_3 \lt 6$$$) и $$$a$$$ станет $$$[6, 8, 8, 1]$$$.

Вы можете выполнять столько операций, сколько хотите. Можете ли вы достичь массива $$$b_1, \ldots, b_n$$$?

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

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

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

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

Сумма $$$n$$$ по всем наборам входных данных не превосходит $$$200\,000$$$.

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

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

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

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

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

  • выбираем $$$x=2$$$, $$$a$$$ становится $$$[2, 0, 0, 0]$$$
  • выбираем $$$x=2$$$, $$$a$$$ становится $$$[2, 2, 0, 0]$$$
  • выбираем $$$x=3$$$, $$$a$$$ становится $$$[5, 2, 0, 0]$$$
  • выбираем $$$x=4$$$, $$$a$$$ становится $$$[5, 6, 0, 0]$$$
  • выбираем $$$x=1$$$, $$$a$$$ становится $$$[5, 6, 1, 0]$$$
  • выбираем $$$x=1$$$, $$$a$$$ становится $$$[5, 6, 1, 1]$$$

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