У Монокарпа был массив \(a\), состоящий из целых чисел. Изначально массив был пустым.
Монокарп выполнял три типа запросов к этому массиву:
- выбрать число и добавить его в конец массива. Каждый раз, когда Монокарп выполнял этот запрос, он выписывал символ +;
- удалить последний элемент из массива. Каждый раз, когда Монокарп выполнял этот запрос, он выписывал символ -. Монокарп не выполнял этот запрос, если массив был пуст;
- проверить, отсортирован ли массив в порядке неубывания, т. е. выполняется ли \(a_1 \le a_2 \le \dots \le a_k\), где \(k\) — количество элементов в массиве на данный момент. Любой массив, содержащий меньше \(2\) элементов, считается отсортированным. Если массив отсортирован в момент запроса, Монокарп выписывал символ 1. Иначе он выписывал символ 0.
Вам задана строка \(s\), состоящая из \(q\) символов 0, 1, + и/или -. Это символы, выписанные Монокарпом, строго в том порядке, в каком он их выписывал.
Вам нужно выяснить, является ли эта строка непротиворечивой, т. е. мог ли Монокарп выполнять такие запросы, что выписанная после них строка равна строке \(s\).
Выходные данные
Для каждого набора входных данных выведите YES, если Монокарп мог выполнить такие запросы, в результате которых будет выписана строка \(s\). Иначе выведите NO.
Вы можете выводить символы в ответе в любом регистре.
Примечание
В первом наборе входных данных Монокарп мог выполнить следующие запросы:
- добавить число \(13\);
- добавить число \(37\);
- проверить, что массив \([13, 37]\) отсортирован в порядке неубывания (и он действительно отсортирован).
В пятом наборе входных данных Монокарп мог выполнить следующие запросы:
- добавить число \(3\);
- добавить число \(2\);
- проверить, что массив \([3, 2]\) отсортирован (он не отсортирован);
- удалить последний элемент;
- добавить число \(3\);
- проверить, что массив \([3, 3]\) отсортирован (он отсортирован);
- удалить последний элемент;
- добавить число \(-5\);
- проверить, что массив \([3, -5]\) отсортирован (он не отсортирован);
В остальных наборах входных данных Монокарп не мог выписать строку \(s\), выполняя свои запросы.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
7
++1
+++1--0
+0
0
++0-+1-+0
++0+-1+-0
+1-+0
|
YES
NO
NO
NO
YES
NO
NO
|