B. Красивые числа
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дана перестановка $$$p=[p_1, p_2, \ldots, p_n]$$$ целых чисел от $$$1$$$ до $$$n$$$. Назовем число $$$m$$$ ($$$1 \le m \le n$$$) красивым, если существует два индекса $$$l, r$$$ ($$$1 \le l \le r \le n$$$), таких что $$$[p_l, p_{l+1}, \ldots, p_r]$$$ это перестановка чисел $$$1, 2, \ldots, m$$$.

Например, пусть $$$p = [4, 5, 1, 3, 2, 6]$$$. В этом случае числа $$$1, 3, 5, 6$$$ красивые, а $$$2, 4$$$ нет. Это так, потому что:

  • если $$$l = 3$$$ и $$$r = 3$$$ мы получим перестановку $$$[1]$$$ для $$$m = 1$$$;
  • если $$$l = 3$$$ и $$$r = 5$$$ мы получим перестановку $$$[1, 3, 2]$$$ для $$$m = 3$$$;
  • если $$$l = 1$$$ и $$$r = 5$$$ мы получим перестановку $$$[4, 5, 1, 3, 2]$$$ для $$$m = 5$$$;
  • если $$$l = 1$$$ и $$$r = 6$$$ мы получим перестановку $$$[4, 5, 1, 3, 2, 6]$$$ для $$$m = 6$$$;
  • невозможно взять некоторые $$$l$$$ и $$$r$$$, так что $$$[p_l, p_{l+1}, \ldots, p_r]$$$ будет перестановкой чисел $$$1, 2, \ldots, m$$$ для $$$m = 2$$$ и для $$$m = 4$$$.

Вам дана перестановка $$$p=[p_1, p_2, \ldots, p_n]$$$. Для всех $$$m$$$ ($$$1 \le m \le n$$$) определите, является ли это число красивым или нет.

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

В первой строке находится единственное целое число $$$t$$$ ($$$1 \le t \le 1000$$$)  — количество тестовых случаев. В следующих строках находятся описания тестовых случаев.

В первой строке описания тестового случая находится единственное целое число $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — длина перестановки $$$p$$$. Следующая строка содержит $$$n$$$ целых чисел $$$p_1, p_2, \ldots, p_n$$$ ($$$1 \le p_i \le n$$$, все $$$p_i$$$ различны) — данная перестановка $$$p$$$.

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

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

Выведите $$$t$$$ строк — ответы на тестовые случаи, в порядке их следования во входных данных.

Ответом на тестовый случай является строка длины $$$n$$$, где $$$i$$$-й символ равен $$$1$$$, если $$$i$$$ это красивое число и равен $$$0$$$ если $$$i$$$ не является красивым числом.

Пример
Входные данные
3
6
4 5 1 3 2 6
5
5 3 1 2 4
4
1 4 3 2
Выходные данные
101011
11111
1001
Примечание

Первый тестовый случай описан в условии задачи.

Во втором тестовом случае все числа от $$$1$$$ до $$$5$$$ красивые:

  • если $$$l = 3$$$ и $$$r = 3$$$ мы получим перестановку $$$[1]$$$ для $$$m = 1$$$;
  • если $$$l = 3$$$ и $$$r = 4$$$ мы получим перестановку $$$[1, 2]$$$ для $$$m = 2$$$;
  • если $$$l = 2$$$ и $$$r = 4$$$ мы получим перестановку $$$[3, 1, 2]$$$ для $$$m = 3$$$;
  • если $$$l = 2$$$ и $$$r = 5$$$ мы получим перестановку $$$[3, 1, 2, 4]$$$ для $$$m = 4$$$;
  • если $$$l = 1$$$ и $$$r = 5$$$ мы получим перестановку $$$[5, 3, 1, 2, 4]$$$ для $$$m = 5$$$.