C. Минимум префикса и максимум суффикса
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дан массив $$$a$$$ из различных целых чисел.

В одной операции вы можете либо:

  • выбрать непустой префикс$$$^{\text{∗}}$$$ массива $$$a$$$ и заменить его на его минимальное значение, или
  • выбрать непустой суффикс$$$^{\text{†}}$$$ массива $$$a$$$ и заменить его на его максимальное значение.

Обратите внимание, что вы можете выбрать весь массив $$$a$$$.

Для каждого элемента $$$a_i$$$ определите, существует ли последовательность операций, чтобы преобразовать $$$a$$$ в $$$[a_i]$$$; то есть сделать так, чтобы массив $$$a$$$ состоял только из одного элемента, который равен $$$a_i$$$. Выведите ваш ответ в виде двоичной строки длины $$$n$$$, где $$$i$$$-й символ равен $$$1$$$, если существует последовательность, чтобы преобразовать $$$a$$$ в $$$[a_i]$$$, и $$$0$$$ в противном случае.

$$$^{\text{∗}}$$$ Префикс массива — это подмассив, состоящий из первых $$$k$$$ элементов массива, для некоторого целого $$$k$$$.

$$$^{\text{†}}$$$ Суффикс массива — это подмассив, состоящий из последних $$$k$$$ элементов массива, для некоторого целого $$$k$$$.

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

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

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$2 \leq n \leq 2\cdot 10^5$$$) — размер массива $$$a$$$.

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел, $$$a_1,a_2,\dots,a_n$$$ ($$$1 \leq a_i \leq 10^6$$$). Гарантируется, что все $$$a_i$$$ различны.

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

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

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

Пример
Входные данные
3
6
1 3 5 4 7 2
4
13 10 12 20
7
1 2 3 4 5 6 7
Выходные данные
100011
1101
1000001
Примечание

В первом примере вы можете сначала выбрать префикс длины $$$3$$$. Затем массив преобразуется в

1472
Далее вы можете выбрать суффикс длины $$$2$$$. Затем массив преобразуется в
147
Наконец, вы можете выбрать префикс длины $$$3$$$. Затем массив преобразуется в
1
Таким образом, мы видим, что возможно преобразовать $$$a$$$ в $$$[1]$$$.

Можно показать, что невозможно преобразовать $$$a$$$ в $$$[3]$$$.