Rating Compression（单调栈，树状数组）

On the competitive programming platform CodeCook, every person has a rating graph described by an array of integers aa of length nn. You are now updating the infrastructure, so you’ve created a program to compress these graphs.

The program works as follows. Given an integer parameter kk, the program takes the minimum of each contiguous subarray of length kk in aa.

More formally, for an array aa of length nn and an integer kk, define the kk-compression array of aa as an array bb of length n−k+1n−k+1, such that

bj=minj≤i≤j+k−1aibj=minj≤i≤j+k−1ai

For example, the 33-compression array of [1,3,4,5,2][1,3,4,5,2] is [min{1,3,4},min{3,4,5},min{4,5,2}]=[1,3,2].[min{1,3,4},min{3,4,5},min{4,5,2}]=[1,3,2].

A permutation of length mm is an array consisting of mm distinct integers from 11 to mm in arbitrary order. For example, [2,3,1,5,4][2,3,1,5,4] is a permutation, but [1,2,2][1,2,2] is not a permutation (22 appears twice in the array) and [1,3,4][1,3,4] is also not a permutation (m=3m=3 but there is 44 in the array).

A kk-compression array will make CodeCook users happy if it will be a permutation. Given an array aa, determine for all 1≤k≤n1≤k≤n if CodeCook users will be happy after a kk-compression of this array or not.

Input

The first line contains a single integer tt (1≤t≤1041≤t≤104) — the number of test cases.

The first line of the description of each test case contains a single integer nn (1≤n≤3⋅1051≤n≤3⋅105) — the length of the array.

The second line of the description of each test case contains nn integers a1,…,ana1,…,an (1≤ai≤n1≤ai≤n) — the elements of the array.

It is guaranteed, that the sum of nn for all test cases does not exceed 3⋅1053⋅105.

Output

For each test case, print a binary string of length nn.

The kk-th character of the string should be 11 if CodeCook users will be happy after a kk-compression of the array aa, and 00 otherwise.

Example

input

Copy

5
5
1 5 3 4 2
4
1 3 2 1
5
1 3 3 3 2
10
1 2 3 4 5 6 7 8 9 10
3
3 3 2

output

Copy

10111
0001
00111
1111111111
000

Note

In the first test case, a=[1,5,3,4,2]a=[1,5,3,4,2].

• The 11-compression of aa is [1,5,3,4,2][1,5,3,4,2] and it is a permutation.
• The 22-compression of aa is [1,3,3,2][1,3,3,2] and it is not a permutation, since 33 appears twice.
• The 33-compression of aa is [1,3,2][1,3,2] and it is a permutation.
• The 44-compression of aa is [1,2][1,2] and it is a permutation.
• The 55-compression of aa is [1][1] and it is a permutation.

思路：

详细思路请看代码

代码：

int n;
struct bit{
    int sum[maxj];
    int lowbit(int x){return x&-x;}
    void add(int x,int c){while(x>n;
    // struct tree;
    for(int i=1;i>a[i];
        ans[i]=l[i]=r[i]=vis[i]=0;
        len[i].clear();
        tree.sum[i]=0;//初始化
    }
    stackst;
    //有大小关系，而且是On的，单调栈
    for(int i=1;i<=n;++i){
        while(st.size()&&a[i]=1;--i){
        while(st.size()&&a[i]<=a[st.top()])st.pop();
        if(st.size()==0)r[i]=n;
        else r[i]=st.top()-1;
        st.push(i);
    }
    for(int i=1;i=1;--i){
        for(auto vv:len[i]){//从后往前，1 然后 2.。
            vis[vv]++;
            if(vis[vv]==1)tree.add(vv,1);
        }
        int sum=tree.getsum(n-i+1);//从前往后
        if(sum>=n-i+1)ans[i]=1;

    }
    for(int i=1;i<=n;++i){
        cout<