B. Сохраняем массив красивым
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Массив $$$[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$$$ в массив или нет.

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

Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных.

Каждый набор входных данных состоит из двух строк. Первая строка содержит одно целое число $$$q$$$ ($$$1 \le q \le 2 \cdot 10^5$$$) — количество запросов. Вторая строка содержит $$$q$$$ целых чисел $$$x_1, x_2, \dots, x_q$$$ ($$$0 \le x_i \le 10^9$$$).

Дополнительное ограничение на входные данные: сумма $$$q$$$ по всем наборам входных данных не превышает $$$2 \cdot 10^5$$$.

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

Для каждого набора входных данных выведите одну строку, состоящую из ровно $$$q$$$ символов. $$$i$$$-й символ строки должен быть 1, если вы добавили число в массив во время $$$i$$$-го запроса; в противном случае он должен быть 0.

Пример
Входные данные
3
9
3 7 7 9 2 4 6 3 4
5
1 1 1 1 1
5
3 2 1 2 3
Выходные данные
111110010
11111
11011
Примечание

Рассмотрим первый набор входных данных из примера. Изначально массив пустой: $$$[]$$$.

  • пытаемся приписать $$$3$$$. Массив $$$[3]$$$ является красивым, поэтому мы добавляем $$$3$$$;
  • пытаемся приписать $$$7$$$. Массив $$$[3, 7]$$$ является красивым, поэтому мы добавляем $$$7$$$;
  • пытаемся приписать $$$7$$$. Массив $$$[3, 7, 7]$$$ является красивым, поэтому мы добавляем $$$7$$$;
  • пытаемся приписать $$$9$$$. Массив $$$[3, 7, 7, 9]$$$ является красивым, поэтому мы добавляем $$$9$$$;
  • пытаемся приписать $$$2$$$. Массив $$$[3, 7, 7, 9, 2]$$$ является красивым, поэтому мы добавляем $$$2$$$;
  • пытаемся приписать $$$4$$$. Массив $$$[3, 7, 7, 9, 2, 4]$$$ не является красивым, поэтому мы не добавляем $$$4$$$;
  • пытаемся приписать $$$6$$$. Массив $$$[3, 7, 7, 9, 2, 6]$$$ не является красивым, поэтому мы не добавляем $$$6$$$;
  • пытаемся приписать $$$3$$$. Массив $$$[3, 7, 7, 9, 2, 3]$$$ является красивым, поэтому мы добавляем $$$3$$$;
  • пытаемся приписать $$$4$$$. Массив $$$[3, 7, 7, 9, 2, 3, 4]$$$ не является красивым, поэтому мы не добавляем $$$4$$$.