B. Часовой механизм
ограничение по времени на тест
1.5 секунд
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У вас есть последовательность из $$$n$$$ часов, расположенных в ряд, где начальное время на $$$i$$$-х часах равно $$$a_i$$$. Каждую секунду по порядку происходит следующее:

  • Время на каждых часах уменьшается на $$$1$$$. Если время на каких-то часах достигает $$$0$$$, вы немедленно проигрываете.
  • Вы можете перейти к соседним часам или остаться на тех же часах, на которых вы находитесь в данный момент.
  • Вы можете сбросить время часов, на которых находитесь, обратно на их начальное значение $$$a_i$$$.

Обратите внимание, что вышеуказанные события происходят по порядку. Если время на часах достигает $$$0$$$ в определенную секунду, даже если вы можете переместиться к этим часам и сбросить их время в течение этой секунды, вы всё равно проиграете.

Вы можете начать с любых часов. Определите, возможно ли продолжать этот процесс бесконечно, не проигрывая.

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

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

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

Вторая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$) — начальные времена, установленные на часах.

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

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

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

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

Пример
Входные данные
5
2
4 10
2
2 2
3
4 10 5
3
5 3 5
5
12 13 25 17 30
Выходные данные
YES
NO
NO
YES
YES
Примечание

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

В третьем наборе входных данных предположим, что вы начинаете с часов $$$1$$$ и следуете стратегии ниже:

Изначально, $$$a=[4,10,5]$$$.

  1. $$$a$$$ становится $$$[3, 9, 4]$$$. Вы перемещаетесь к часам $$$2$$$ и сбрасываете их время, в результате чего $$$a=[3, 10, 4]$$$.
  2. $$$a$$$ становится $$$[2, 9, 3]$$$. Вы перемещаетесь к часам $$$3$$$ и сбрасываете их время, в результате чего $$$a=[2, 9, 5]$$$.
  3. $$$a$$$ становится $$$[1, 8, 4]$$$. Вы перемещаетесь к часам $$$2$$$ и сбрасываете их время, в результате чего $$$a=[1, 10, 4]$$$.
  4. $$$a$$$ становится $$$[0, 9, 3]$$$. Вы перемещаетесь к часам $$$1$$$, но проигрываете, потому что $$$a_1$$$ достигает $$$0$$$.

Можно доказать, что никакая другая стратегия также не позволяет вам продолжать этот процесс бесконечно.