链接：https://codeforces.com/contest/1265/problem/B

You are given a permutation p=[p1,p2,…,pn]p=[p1,p2,…,pn] of integers from 11 to nn. Let's call the number mm (1≤m≤n1≤m≤n) beautiful, if there exists two indices l,rl,r (1≤l≤r≤n1≤l≤r≤n), such that the numbers [pl,pl+1,…,pr][pl,pl+1,…,pr] is a permutation of numbers 1,2,…,m1,2,…,m.

For example, let p=[4,5,1,3,2,6]p=[4,5,1,3,2,6]. In this case, the numbers 1,3,5,61,3,5,6 are beautiful and 2,42,4 are not. It is because:

  • if l=3l=3 and r=3r=3 we will have a permutation [1][1] for m=1m=1;
  • if l=3l=3 and r=5r=5 we will have a permutation [1,3,2][1,3,2] for m=3m=3;
  • if l=1l=1 and r=5r=5 we will have a permutation [4,5,1,3,2][4,5,1,3,2] for m=5m=5;
  • if l=1l=1 and r=6r=6 we will have a permutation [4,5,1,3,2,6][4,5,1,3,2,6] for m=6m=6;
  • it is impossible to take some ll and rr, such that [pl,pl+1,…,pr][pl,pl+1,…,pr] is a permutation of numbers 1,2,…,m1,2,…,m for m=2m=2 and for m=4m=4.

You are given a permutation p=[p1,p2,…,pn]p=[p1,p2,…,pn]. For all mm (1≤m≤n1≤m≤n) determine if it is a beautiful number or not.

Input

The first line contains the only integer tt (1≤t≤10001≤t≤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 nn (1≤n≤2⋅1051≤n≤2⋅105) — the length of the given permutation pp. The next line contains nnintegers p1,p2,…,pnp1,p2,…,pn (1≤pi≤n1≤pi≤n, all pipi are different) — the given permutation pp.

It is guaranteed, that the sum of nn from all test cases in the input doesn't exceed 2⋅1052⋅105.

Output

Print tt 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 nn, there the ii-th character is equal to 11 if ii is a beautiful number and is equal to 00 if ii is not a beautiful number.

Example

input

Copy

3
6
4 5 1 3 2 6
5
5 3 1 2 4
4
1 4 3 2

output

Copy

101011
11111
1001

Note

The first test case is described in the problem statement.

In the second test case all numbers from 11 to 55 are beautiful:

  • if l=3l=3 and r=3r=3 we will have a permutation [1][1] for m=1m=1;
  • if l=3l=3 and r=4r=4 we will have a permutation [1,2][1,2] for m=2m=2;
  • if l=2l=2 and r=4r=4 we will have a permutation [3,1,2][3,1,2] for m=3m=3;
  • if l=2l=2 and r=5r=5 we will have a permutation [3,1,2,4][3,1,2,4] for m=4m=4;
  • if l=1l=1 and r=5r=5 we will have a permutation [5,3,1,2,4][5,3,1,2,4] for m=5m=5.

代码：

#include <bits/stdc++.h>
using namespace std;
long long n,t;
struct node{
	int a;
	long long id;
}x[1000001];
long long b[1000001];
long long c[1000001]; 
bool cmp(node p,node q)
{
	return p.a<q.a;
}
long long mod=10007;
int main()
{
	cin>>t;
	while(t--)
	{
		cin>>n;
		for(int i=1;i<=n;i++)
		{
			cin>>x[i].a;
			x[i].id=i;
		}
		sort(x+1,x+1+n,cmp);
		b[1]=x[1].id;
		c[1]=x[1].id;
		for(int i=2;i<=n;i++)
		{
			b[i]=min(x[i].id,b[i-1]);
			c[i]=max(x[i].id,c[i-1]);
		}
		for(int i=1;i<=n;i++)
		{
			if(c[i]-b[i]+1==i)
			{
				cout<<1;
			}
			else
			cout<<0;
		}
		cout<<endl;
	}
}