Задана строка \(s\), состоящая только из символов '0' или '1'. Пусть \(|s|\) будет длиной строки \(s\).
Требуется выбрать некоторое целое число \(k\) (\(k > 0\)) и последовательность \(a\) длины \(k\) такую что:
- \(1 \le a_1 < a_2 < \dots < a_k \le |s|\);
- \(a_{i-1} + 1 < a_i\) для всех \(i\) от \(2\) до \(k\).
Символы на позициях \(a_1, a_2, \dots, a_k\) удаляются, оставшиеся символы склеиваются без изменения порядка. То есть, другими словами, позиции в выбранной последовательности \(a\) не должны быть соседними.
Пусть полученная строка будет \(s'\). \(s'\) называется отсортированной, если для всех \(i\) от \(2\) до \(|s'|\) \(s'_{i-1} \le s'_i\).
Существует ли такая последовательность \(a\), что \(s'\) отсортирована?
Выходные данные
На каждый набор входных данных выведите «YES», если существует такая последовательность \(a\), что при удалении символов на позициях \(a_1, a_2, \dots, a_k\) и склеивании оставшихся частей без изменения порядка получится отсортированная строка.
В противном случае выведите «NO».
Вы можете вывести каждую букву в любом регистре (например, YES, Yes, yes, yEs будут распознаны как положительный ответ).
Примечание
В первом наборе входных данных можно выбрать последовательность \(a=[1,3,6,9]\). При удалении подчеркнутых букв из «10101011011» получится строка «0011111», которая отсортирована.
Во втором и в третьем наборах входных данных последовательность уже отсортирована.
В четвертом наборе входных данных можно выбрать последовательность \(a=[3]\). \(s'=\) «11», которая отсортирована.
В пятом наборе входных данных нет способа выбрать последовательность \(a\) так, чтобы \(s'\) была отсортирована.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
10101011011
0000
11111
110
1100
|
YES
YES
YES
YES
NO
|