You are given a permutation $p=[p_1, p_2, \ldots, p_n]$ of integers from $1$ to $n$. Let's call the number $m$ ($1 \le m \le n$) beautiful, if there exists two indices $l, r$ ($1 \le l \le r \le n$), such that the numbers $[p_l, p_{l+1}, \ldots, p_r]$ is a permutation of numbers $1, 2, \ldots, m$.

For example, let $p = [4, 5, 1, 3, 2, 6]$. In this case, the numbers $1, 3, 5, 6$ are beautiful and $2, 4$ are not. It is because:  if $l = 3$ and $r = 3$ we will have a permutation $[1]$ for $m = 1$;  if $l = 3$ and $r = 5$ we will have a permutation $[1, 3, 2]$ for $m = 3$;  if $l = 1$ and $r = 5$ we will have a permutation $[4, 5, 1, 3, 2]$ for $m = 5$;  if $l = 1$ and $r = 6$ we will have a permutation $[4, 5, 1, 3, 2, 6]$ for $m = 6$;  it is impossible to take some $l$ and $r$, such that $[p_l, p_{l+1}, \ldots, p_r]$ is a permutation of numbers $1, 2, \ldots, m$ for $m = 2$ and for $m = 4$. 

You are given a permutation $p=[p_1, p_2, \ldots, p_n]$. For all $m$ ($1 \le m \le n$) determine if it is a beautiful number or not.


-----Input-----

The first line contains the only integer $t$ ($1 \le t \le 1000$)  — the number of test cases in the input. The next lines contain the description of test cases.

The first line of a test case contains a number $n$ ($1 \le n \le 2 \cdot 10^5$) — the length of the given permutation $p$. The next line contains $n$ integers $p_1, p_2, \ldots, p_n$ ($1 \le p_i \le n$, all $p_i$ are different) — the given permutation $p$.

It is guaranteed, that the sum of $n$ from all test cases in the input doesn't exceed $2 \cdot 10^5$.


-----Output-----

Print $t$ lines — the answers to test cases in the order they are given in the input. 

The answer to a test case is the string of length $n$, there the $i$-th character is equal to $1$ if $i$ is a beautiful number and is equal to $0$ if $i$ is not a beautiful number.


-----Example-----
Input
3
6
4 5 1 3 2 6
5
5 3 1 2 4
4
1 4 3 2

Output
101011
11111
1001



-----Note-----

The first test case is described in the problem statement.

In the second test case all numbers from $1$ to $5$ are beautiful:  if $l = 3$ and $r = 3$ we will have a permutation $[1]$ for $m = 1$;  if $l = 3$ and $r = 4$ we will have a permutation $[1, 2]$ for $m = 2$;  if $l = 2$ and $r = 4$ we will have a permutation $[3, 1, 2]$ for $m = 3$;  if $l = 2$ and $r = 5$ we will have a permutation $[3, 1, 2, 4]$ for $m = 4$;  if $l = 1$ and $r = 5$ we will have a permutation $[5, 3, 1, 2, 4]$ for $m = 5$.

Difficulty: interview

Starter code:

Solutions:
for _ in range(int(input())):
    input()
    nums = [int(x) for x in input().split()]
    new_ar = list(zip(nums,[i for i in range(len(nums))]))
    new_ar.sort()
    
    maxx = new_ar[0][1]
    minn = new_ar[0][1]
    s="1"
    for j in range(1,len(new_ar)):
        if(new_ar[j][1]>maxx):
            maxx = new_ar[j][1]
        if(new_ar[j][1]<minn):
            minn = new_ar[j][1]
        if(maxx-minn<j+1):
            s+="1"
        else:
            s+="0"
        
    print(s)

import sys
def I():
        return sys.stdin.readline().rstrip()

for _ in range(int(I())):
    n = int(I())
    l = list(map(int,I().split()))
    r = list(range(n))
    r.sort(key=lambda x: l[x])
    mn, mx = None, None
    for i in range(n):
        if mn is None:
            mn = mx = r[ i ]
        else:
            mn = min( mn, r[ i ] )
            mx = max( mx, r[ i ] )
        l[ i ] = '1' if mx - mn == i else '0'
    print("".join(l))


from sys import stdin
def rl():
    return [int(w) for w in stdin.readline().split()]

k, = rl()
for _ in range(k):
    n, = rl()
    p = rl()

    q = [0] * n
    for i, x in enumerate(p):
        q[x-1] = i

    l = r = q[0]
    m = []
    for k, i in enumerate(q):
        if i < l:
            l = i
        elif i > r:
            r = i
        m.append('1' if r - l == k else '0')
    print(''.join(m))


# @author 

import sys

class BBeautifulNumbers:
    def solve(self):
        for _ in range(int(input())):
            n = int(input())
            p = [int(_) - 1 for _ in input().split()]

            mn_index = [float('inf')] * n
            mx_index = [-float('inf')] * n
            prev = [0] * n
            for i in range(n):
                prev[p[i]] = i
            # print(prev)
            for i in range(n):
                mn_index[i] = min(mn_index[i - 1], prev[i])
                mx_index[i] = max(mx_index[i - 1], prev[i])

            ans = ['0'] * n
            # print(mn_index, mx_index)
            for i in range(n):
                l, r = mn_index[i], mx_index[i]
                ans[i] = '1' if r - l + 1 == i + 1 else '0'

            print(''.join(ans))

solver = BBeautifulNumbers()
input = sys.stdin.readline

solver.solve()


def f(L):
    n=len(L)
    M=[0]*(len(L)+1)
    for i in range(len(L)):
        M[L[i]]=i
    s=[0]*len(L)
    s[0]=1
    sumof=M[1]
    mx=M[1]
    mi=M[1]
    for i in range(2,n):
        k=M[i]
        if k>mx:mx=k
        if k<mi:mi=k
        sumof+=k
        if sumof==(mx*(mx+1))//2-((mi-1)*mi)//2:
            s[i-1]=1
    s[n-1]=1
    return s
for i in ' '*int(input()):
    n=int(input())
    s=f(list(map(int,input().split())))
    for i in s:print(i,end='')
    print()

t=int(input())
for _ in range(t):
    n=int(input())
    a=list(map(int,input().split()))
    pos=[0 for i in range(n+1)]
    for i in range(n):
        pos[a[i]]=i
    ans=[-1 for i in range(n)]
    ans[0]=1
    l,r=pos[1],pos[1]
    for i in range(2,n+1):
        l=min(l,pos[i])
        r=max(r,pos[i])
        if r-l==i-1:
            ans[i-1]=1
        else:
            ans[i-1]=0
    print("".join(map(str,ans)))

t = int(input())

for t_i in range(t):
    n = int(input())
    P = input().split()
    l, r = -1, -1
    for i in range(n):
        P[i] = int(P[i])
        if P[i] == 1:
            l = i
            r = i
    max_seen = 1
    beaut = ['1']
    for _ in range(n - 1):
        if l == 0:
            l_cand = 10**8
        else:
            l_cand = P[l - 1]
        if r == n - 1:
            r_cand = 10**8
        else:
            r_cand = P[r + 1]
        if r_cand > l_cand:
            l -= 1
            max_seen = max(l_cand, max_seen)
        else:
            r += 1
            max_seen = max(r_cand, max_seen)
        beaut.append('1' if max_seen == r - l + 1 else '0')
    print(''.join(beaut))
            


for _ in range(int(input())):
    n = int(input())
    a = list(map(int,input().split()))
    d = {}
    for i in range(n):
        d[a[i]] = i

    ans = ''
    mn = 200001
    mx = -1
    for i in range(1,n+1):
        if(mn > d[i]):
            mn = d[i]
        if(mx < d[i]):
            mx = d[i]

        
        if(mx - mn + 1 > i):
            ans += '0'

        else:
            ans += '1'


    print(ans)


from math import *
from collections import *
import sys
sys.setrecursionlimit(10**9)

t = int(input())
for y in range(t):
	n = int(input())
	a = list(map(int,input().split()))
	ans = ['1']
	le = 1
	l = a.index(1)
	l -= 1
	r = l + 2
	m = 1
	while(le < n):
		if(l != -1 and r != n):
			if(a[l] > a[r]):
				m = max(m,a[r])
				r += 1
				if(m == le+1):
					ans.append('1')
				else:
					ans.append('0')
			else:
				m = max(m,a[l])
				l -= 1
				if(m == le+1):
					ans.append('1')
				else:
					ans.append('0')
		elif(l != -1):
			m = max(m,a[l])
			l -= 1
			if(m == le+1):
				ans.append('1')
			else:
				ans.append('0')
		else:
			m = max(m,a[r])
			r += 1
			if(m == le+1):
				ans.append('1')
			else:
				ans.append('0')
		le += 1
	print("".join(ans))





t = int(input())
for _ in range(t):
    n = int(input())
    a = list(map(int, input().split()))
    pos = [0]*(n+1)
    for i, x in enumerate(a):
        pos[x] = i

    used = [0, 1] + [0]*n
    ans = [0]*n
    l, r = pos[1], pos[1]
    count = 1

    for x in range(1, n+1):
        if not used[x]:
            if pos[x] < l:
                while not used[x]:
                    l -= 1
                    used[a[l]] = 1
                    count += 1
            else:
                while not used[x]:
                    r += 1
                    used[a[r]] = 1
                    count += 1

        if count == x:
            ans[x-1] = 1

    print(*ans, sep='')

def mi():
    return map(int, input().split())

'''
3
6
4 5 1 3 2 6
5
5 3 1 2 4
4
1 4 3 2
3
6
4 5 1 3 2 6
5
5 3 1 2 4
4
1 4 3 2
'''
for _ in range(int(input())):
    n = int(input())
    a = list(mi())
    t = a.index(1)
    dist = [0]*(n+1)
    dic = [0]*n
    for i in range(n):
        dist[a[i]] = abs(t-i)
        dic[i] = [a[i], i]
    dic.sort()
    lm = dic[0][1]
    rm = dic[0][1]
    print (1, end = '')
    for i in range(1, n):
        if (dic[i][1]<lm):
            lm = dic[i][1]
        if (dic[i][1]>rm):
            rm = dic[i][1]
        if rm-lm<i+1:
            print (1, end = '')
        else:
            print (0, end = '')
    print()

from sys import stdin
input = stdin.readline


t = int(input())

for _ in range(t):

    n = int(input())
    a = list(map(int,input().split()))

    start = 0
    for i,v in enumerate(a):
        if v == 1:
            start = i
            break
    ans = [0]*-~n
    ans[n-1] = 1
    mx = 1
    l = start
    r = start

    def move(x):
        nonlocal l,r,mx
        if x:
            mx = max(a[r+1],mx)
            r += 1
        else:
            mx = max(a[l-1],mx)
            l -= 1


    while mx < n:
        if mx == r-l+1:
            ans[mx-1] = 1
        if l == 0:
            move(1)
        elif r == n-1:
            move(0)
        else:
            if a[l-1] > a[r+1]:
                move(1)
            else:
                move(0)

    print("".join(map(str,ans[:n])))





















#!/usr/bin/env python3
from itertools import combinations
import sys
input = sys.stdin.readline
INF = 10**9

t = int(input())
for i in range(t):
    n = int(input())
    a = [INF] + [int(item) for item in input().split()] + [INF]
    ans = [1]
    l = r = a.index(1)
    max_val = 1
    for i in range(2, n+1):
        if i == max(max_val, a[l-1]):
            ans.append(1)
            l -= 1
            max_val = i
        elif i == max(max_val, a[r+1]):
            ans.append(1)
            r += 1
            max_val = i
        elif a[l-1] < a[r+1]:
            ans.append(0)
            max_val = max(max_val, a[l-1])
            l -= 1
        else:
            ans.append(0)
            max_val = max(max_val, a[r+1])
            r += 1
    print("".join([str(item) for item in ans]))

for j in range(int(input())):
    n = int(input())
    c = list(map(int,input().split()))
    index = [0]*n
    for i in range(n):
        index[c[i]-1]=i
    ma = 0
    mi = n
    ans = ['0']*n
    # print(index)
    for k in range(n):
        ma = max(index[k],ma)
        mi = min(index[k],mi)
        #print(k,mr,index[k]-index[0])
        if ma-mi<=k:
            ans[k]='1'
    print(''.join(ans))

q=int(input())
for t in range(q):
    n=int(input())
    a=list(map(int,input().split()))
    ma=1
    ans='1'
    uk1=a.index(1)
    uk2=uk1
    while uk2-uk1+1!=n:
        if uk2==n-1:
            uk1-=1
            ma=max(ma,a[uk1])
            if ma==uk2-uk1+1:
                ans=ans+'1'
            else:
                ans=ans+'0'
        else:
            if uk1==0:
                uk2+=1
                ma=max(ma,a[uk2])
                if ma == uk2 - uk1 + 1:
                    ans = ans + '1'
                else:
                    ans=ans+'0'
            else:
                if a[uk1-1]<a[uk2+1]:
                    uk1 -= 1
                    ma = max(ma, a[uk1])
                    if ma == uk2 - uk1 + 1:
                        ans = ans + '1'
                    else:
                        ans = ans + '0'
                else:
                    uk2 += 1
                    ma = max(ma, a[uk2])
                    if ma == uk2 - uk1 + 1:
                        ans = ans + '1'
                    else:
                        ans = ans + '0'
    print(ans)


lpn = int(input())

for loop in range(lpn):

    n = int(input())
    p = list(map(int,input().split()))

    for i in range(n):

        if p[i] == 1:
            oneind = i
            break

    l = oneind
    r = oneind
    nmax = 1
    ans = [0] * n
    ans[0] = 1

    for i in range(n-1):

        if l == 0 or( r != n-1 and p[l-1] > p[r+1]):
            r += 1
            nmax = max(nmax,p[r])
            if i+2 == nmax:
                ans[i+1] = 1 
        else:
            l -= 1
            nmax = max(nmax,p[l])

            if i+2 == nmax:
                ans[i+1] = 1 
            
    print("".join(map(str,ans)))


t = int(input())
for i in range(t):
    n = int(input())
    a = [int(i) for i in input().split()]
    ans = ['0'] * n
    ans[0] = '1'
    ans[-1] = '1'
    l = 0
    r = n - 1
    now = n
    while (r - l) > 1:
        if a[r] > now:
            r -= 1
            continue
        if a[l] > now:
            l += 1
            continue
        if (r - l + 1) == now:
            ans[r - l] = '1'
        now -= 1
    if (r - l  + 1) == now:
        ans[r - l] = '1'
    print(''.join(ans))




# https://codeforces.com/contest/1265/problem/B

def main():
    n = int(input())
    p = list(map(int, input().split()))
    idx = [0] * n
    for i in range(n):
        idx[p[i]-1] = i
    ans = ''
    left = n
    right = 0
    for i in range(n):
        left = min(left, idx[i])
        right = max(right, idx[i])
        if right - left == i:
            ans += '1'
        else:
            ans += '0'
    return ans

t = int(input())
for i in range(t):
    print(main())


def f():
    n = int(input())
    A = [int(s) for s in input().split()]
    ans = [0]*n
    ans[0] = 1
    ans[n-1] = 1
    i = 0
    j = n-1
    outMin = n+1
    while j>i:
        if A[i] > A[j]:
            if A[i] < outMin:
                outMin = A[i]
            i += 1
        else:
            if A[j] < outMin:
                outMin = A[j]
            j -= 1
        if j-i == outMin-2:
            ans[j-i] = 1
    print(''.join(str(i) for i in ans))


t = int(input())
for i in range(t):
    f()

n = int(input())
for _ in range(n):
    k = int(input())
    pos = [0] * k
    arr = list(map(int, input().split(' ')))
    for i in range(k):
        pos[arr[i] - 1] = i

    #print(pos)

    left, right = [0] * k, [0] * k
    left[0], right[0] = pos[0], pos[0]
    for i in range(1, k):
        left[i] = min(left[i - 1], pos[i])
        right[i] = max(right[i - 1], pos[i])

    #print(left)
    #print(right)
    for i in range(k):
        if right[i] - left[i] == i:
            print(1, end="")
        else:
            print(0, end="")
    print()

for kkk in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	d = {}
	for i in range(n):
		d[l[i]] = i
	ans = ["0" for i in range(n+1)]
	ans[1] = "1"
	posleft = d[1]
	posright = d[1]
	for j in range(2, n+1):
		if(d[j]==posleft-1 or d[j]==posright+1):
			if(ans[j-1]=="1"):
				ans[j] = "1"
		elif(d[j]<posright and d[j]>posleft):
			if(posright - posleft + 1 == j):
				ans[j] = "1"
		if(d[j]<posleft):
			posleft = d[j]
		if(d[j]>posright):
			posright = d[j]
	print(''.join(ans[1:]))

import sys
import math
import bisect
 
 
sys.setrecursionlimit(1000000000)
def input():
    return sys.stdin.readline().strip()
 
def iinput():
    return int(input())
 
def finput():
    return float(input())
 
def tinput():
    return input().split()
 
def rinput():
    return map(int, tinput())
 
def rlinput():
    return list(rinput())

def main():
    n = iinput()
    c = rlinput()
    q, res, w, e = [0] * n, ['0'] * n, 0, n
    for i in range(n):
        q[c[i] - 1] = i
    for i in range(n):
        w = max(q[i], w)
        e = min(q[i], e)
        if w <= i + e:
            res[i] = '1'
    print(''.join(res))
        
for j in range(int(input())):
    main()

from math import floor, ceil

t = int(input())

for _ in range(t):
    n = int(input())
    a = list(map(int, input().split()))
    pos = dict()
    for p, i in enumerate(a):
        pos[i] = p
    minpos = [None] + [pos[1]] + [None]*(n-1)
    maxpos = [None] + [pos[1]] + [None]*(n-1)

    for i in range(2, n+1):
        minpos[i] = min(minpos[i-1], pos[i])
        maxpos[i] = max(maxpos[i-1], pos[i])


    good = ['0']*n 
    for i in range(1, n+1):
        if maxpos[i] - minpos[i] + 1 == i:
            good[i-1] = '1'

    print(''.join(good))