Вам дана перестановка \(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\) строк — ответы на тестовые случаи, в порядке их следования во входных данных.
Ответом на тестовый случай является строка длины \(n\), где \(i\)-й символ равен \(1\), если \(i\) это красивое число и равен \(0\) если \(i\) не является красивым числом.
Примечание
Первый тестовый случай описан в условии задачи.
Во втором тестовом случае все числа от \(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\).