Массив \([a_1, a_2, \dots, a_k]\) называется красивым, если можно удалить несколько (возможно, ноль) элементов из начала массива и вставить все эти элементы в конец массива в том же порядке таким образом, чтобы получившийся массив был отсортирован в неубывающем порядке.
Другими словами, массив \([a_1, a_2, \dots, a_k]\) является красивым, если существует целое число \(i \in [0, k-1]\), такое что массив \([a_{i+1}, a_{i+2}, \dots, a_{k-1}, a_k, a_1, a_2, \dots, a_i]\) отсортирован в неубывающем порядке.
Например:
- \([3, 7, 7, 9, 2, 3]\) является красивым: мы можем удалить первые четыре элемента и вставить их в конец в том же порядке, и мы получим массив \([2, 3, 3, 7, 7, 9]\), который отсортирован в неубывающем порядке;
- \([1, 2, 3, 4, 5]\) является красивым: мы можем не удалять ни одного элемента и вставить их в конец, и мы получим массив \([1, 2, 3, 4, 5]\), который отсортирован в неубывающем порядке;
- \([5, 2, 2, 1]\) не является красивым.
Обратите внимание, что любой массив, состоящий из нуля или одного элемента, является красивым.
Дан пустой массив \(a\). Вам нужно обработать \(q\) запросов к нему. Во время \(i\)-го запроса вам будет дано одно целое число \(x_i\), и вы должны сделать следующее:
- если вы можете добавить \(x_i\) в конец массива \(a\) так, чтобы массив \(a\) оставался красивым, вы должны добавить его;
- в противном случае вы не должны делать ничего.
После каждого запроса сообщите, добавили вы число \(x_i\) в массив или нет.
Выходные данные
Для каждого набора входных данных выведите одну строку, состоящую из ровно \(q\) символов. \(i\)-й символ строки должен быть 1, если вы добавили число в массив во время \(i\)-го запроса; в противном случае он должен быть 0.