A. Добрый плотник
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод
I would use a firework to announce, a wave to bid farewell, and a bow to say thanks: bygones are bygones; not only on the following path will I be walking leisurely and joyfully, but also the footsteps won't halt as time never leaves out flowing; for in the next year, we will meet again.
— Cocoly1990, Goodbye 2022

В своем сне Коколи отправился в длительный беззаботный отпуск. Он захотел попробовать себя в новых сферах, например... стать плотником. Чтобы научиться этому искусству, Коколи решил стать учеником Мастера, но перед ним встала трудная задача, которую ему предстоит решить.

Коколи даётся массив $$$a_1, a_2,\ldots, a_n$$$. Мастер называет набор целых чисел $$$S$$$ стабильным тогда и только тогда, когда для любых $$$u$$$, $$$v$$$ и $$$w$$$ из множества $$$S$$$ (обратите внимание, что $$$u$$$, $$$v$$$ и $$$w$$$ не обязательно должны быть попарно различными), палочки длины $$$u$$$, $$$v$$$ и $$$w$$$ могут образовать невырожденный треугольник$$$^{\text{∗}}$$$.

Коколи предлагается разбить массив $$$a$$$ на несколько (возможно, $$$1$$$ или $$$n$$$) непустых непрерывных подотрезков$$$^{\text{†}}$$$, таким образом, чтобы для каждого из подотрезков набор, содержащий все элементы в нём, был стабильным.

Мастер хочет, чтобы Коколи разбил $$$a$$$ на подотрезки по крайней мере двумя различными$$$^{\text{‡}}$$$ способами. Вы должны помочь ему определить, возможно ли это.

$$$^{\text{∗}}$$$Треугольник с длинами сторон $$$x$$$, $$$y$$$ и $$$z$$$ называется невырожденным тогда и только тогда, когда:

  • $$$x + y > z$$$,
  • $$$y + z > x$$$, и
  • $$$z + x > y$$$.

$$$^{\text{†}}$$$Последовательность $$$b$$$ является подотрезком последовательности $$$c$$$, если $$$b$$$ может быть получена из $$$c$$$ удалением нескольких (возможно, ни одного или всех) элементов с начала и нескольких (возможно, ни одного или всех) элементов с конца.

$$$^{\text{‡}}$$$Два разбиения считаются различными тогда и только тогда, когда выполняется хотя бы одно из следующих условий:

  • количество непрерывных подотрезков в двух разбиениях различно;
  • существует целое число $$$k$$$, такое, что длины $$$k$$$-го подотрезка в двух разбиениях различны.
Входные данные

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

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

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

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

Для каждого набора входных данных выведите $$$\texttt{YES}$$$, если существует по крайней мере два способа разбиения $$$a$$$, и $$$\texttt{NO}$$$ в противном случае.

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

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

В первом наборе входных данных можно привести в пример такие два разбиения:

  • $$$[2, 3], [5, 7]$$$, поскольку
    • $$$[2, 3]$$$ стабильный: палочки с длинами $$$(2, 2, 2), (2, 2, 3), (2, 3, 3), (3, 3, 3)$$$ образовывают невырожденные треугольники.
    • $$$[5, 7]$$$ стабильный: палочки с длинами $$$(5, 5, 5), (5, 5, 7), (5, 7, 7), (7, 7, 7)$$$ образовывают невырожденные треугольники.
  • и $$$[2], [3, 5], [7]$$$, поскольку
    • $$$[2]$$$ стабильный: палочки с длинами $$$(2, 2, 2)$$$ образовывают невырожденный треугольник.
    • $$$[3, 5]$$$ стабильный: палочки с длинами $$$(3, 3, 3), (3, 3, 5), (3, 5, 5), (5, 5, 5)$$$ образовывают невырожденные треугольники.
    • $$$[7]$$$ стабильный: палочки с длинами $$$(7, 7, 7)$$$ образовывают невырожденный треугольник.

Обратите внимание, что некоторые другие разбиения также удовлетворяют ограничениям. Например, $$$[2], [3], [5], [7]$$$ и $$$[2], [3], [5, 7]$$$.

Во втором наборе входных данных Коколи может только разбить элементы на отдельные подотрезки, что приводит к разбиению $$$[115], [9], [2], [28]$$$. Поскольку у нас есть только одно возможное разбиение, то ответ — $$$\texttt{NO}$$$.

В третьем наборе входных данных обратите внимание, что разбиение $$$[8, 4], [1], [6], [2]$$$ не удовлетворяет ограничениям, поскольку $$$\{8, 4\}$$$ не является стабильным множеством: палочки $$$4$$$, $$$4$$$ и $$$8$$$ не образовывают невырожденный треугольник.