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.
В своем сне Коколи отправился в длительный беззаботный отпуск. Он захотел попробовать себя в новых сферах, например... стать плотником. Чтобы научиться этому искусству, Коколи решил стать учеником Мастера, но перед ним встала трудная задача, которую ему предстоит решить.
Коколи даётся массив \(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{‡}}\) способами. Вы должны помочь ему определить, возможно ли это.
Выходные данные
Для каждого набора входных данных выведите \(\texttt{YES}\), если существует по крайней мере два способа разбиения \(a\), и \(\texttt{NO}\) в противном случае.
Вы можете выводить каждую букву в любом регистре (строчную или заглавную). Например, строки \(\texttt{yEs}\), \(\texttt{yes}\), \(\texttt{Yes}\) и \(\texttt{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\) не образовывают невырожденный треугольник.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|