D. Сжатие рейтинга
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

На платформе CodeCook для соревнований по спортивному программированию у каждого человека есть график его рейтинга, описываемый массивом целых чисел $$$a$$$ длины $$$n$$$. Вы обновляете инфраструктуру, поэтому вы создали программу, сжимающую эти графики.

Программа работает следующим образом. Задается целое число $$$k$$$. Программа берет минимум на каждом последовательном подмассиве длины $$$k$$$ в массиве $$$a$$$.

Более формально, для массива $$$a$$$ длины $$$n$$$ и целого числа $$$k$$$, определим $$$k$$$-сжатие массива $$$a$$$ как массив $$$b$$$ длины $$$n-k+1$$$, такой что $$$$$$b_j =\min_{j\le i\le j+k-1}a_i$$$$$$

Например, $$$3$$$-сжатие массива $$$[1, 3, 4, 5, 2]$$$ это $$$[\min\{1, 3, 4\}, \min\{3, 4, 5\}, \min\{4, 5, 2\}]=[1, 3, 2].$$$

Перестановка длины $$$m$$$ это массив, состоящий из $$$m$$$ различных целых чисел от $$$1$$$ до $$$m$$$ в некотором порядке. Например, $$$[2,3,1,5,4]$$$ это перестановка, но $$$[1,2,2]$$$ это не перестановка ($$$2$$$ встречается дважды в массиве) и $$$[1,3,4]$$$ это тоже не перестановка ($$$m=3$$$, но в массиве есть число $$$4$$$).

$$$k$$$-сжатие массива рейтинга сделает пользователей CodeCook счастливыми, если оно будет перестановкой. Вам дан массив $$$a$$$, определите для всех $$$1\leq k\leq n$$$ будут ли счастливы пользователи CodeCook после $$$k$$$-сжатия этого массива или нет.

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

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

В первой строке описания каждого набора входных данных находится единственное целое число $$$n$$$ ($$$1\leq n\leq 3\cdot 10^5$$$) — длина массива.

Во второй строке описания каждого набора входных данных находится $$$n$$$ целых чисел $$$a_1,\ldots,a_n$$$ ($$$1\leq a_i\leq n$$$) — элементы массива.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$3\cdot 10^5$$$.

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

Для каждого набора входных данных выведите бинарную строку длины $$$n$$$.

$$$k$$$-й символ строки должен быть $$$1$$$, если пользователи CodeCook будут счастливы после $$$k$$$-сжатия массива $$$a$$$ и $$$0$$$, иначе.

Пример
Входные данные
5
5
1 5 3 4 2
4
1 3 2 1
5
1 3 3 3 2
10
1 2 3 4 5 6 7 8 9 10
3
3 3 2
Выходные данные
10111
0001
00111
1111111111
000
Примечание

В первом наборе входных данных $$$a=[1, 5, 3, 4, 2]$$$.

  • $$$1$$$-сжатие массива $$$a$$$ будет $$$[1, 5, 3, 4, 2]$$$ и это перестановка.
  • $$$2$$$-сжатие массива $$$a$$$ будет $$$[1, 3, 3, 2]$$$ и это не перестановка, потому что $$$3$$$ встречается дважды.
  • $$$3$$$-сжатие массива $$$a$$$ будет $$$[1, 3, 2]$$$ и это перестановка.
  • $$$4$$$-сжатие массива $$$a$$$ будет $$$[1, 2]$$$ и это перестановка.
  • $$$5$$$-сжатие массива $$$a$$$ будет $$$[1]$$$ и это перестановка.