The array [a1,a2,…,ak] is called beautiful if it is possible to remove several (maybe zero) elements from the beginning of the array and insert all these elements to the back of the array in the same order in such a way that the resulting array is sorted in non-descending order.

In other words, the array [a1,a2,…,ak] is beautiful if there exists an integer i∈[0,k?1] such that the array [ai+1,ai+2,…,ak?1,ak,a1,a2,…,ai]

?is sorted in non-descending order.

For example:

[3,7,7,9,2,3] is beautiful: we can remove four first elements and insert them to the back in the same order, and we get the array [2,3,3,7,7,9], which is sorted in non-descending order;

[1,2,3,4,5] is beautiful: we can remove zero first elements and insert them to the back, and we get the array [1,2,3,4,5], which is sorted in non-descending order;

[5,2,2,1] is not beautiful.

Note that any array consisting of zero elements or one element is beautiful.

You are given an array a, which is initially empty. You have to process q queries to it. During the i-th query, you will be given one integer xi, and you have to do the following:

if you can append the integer xi to the back of the array a so that the array a stays beautiful, you have to append it;otherwise, do nothing.

After each query, report whether you appended the given integer xi, or not.

Input

The first line contains one integer t (1≤t≤104) — the number of test cases.

Each test case consists of two lines.?

The first line contains one integer q (1≤q≤2?105) — the number of queries. The second line contains q integers x1,x2,…,xq (0≤xi≤109).

Additional constraint on the input: the sum of q over all test cases does not exceed 2?105).

Output

For each test case, print one string consisting of exactly q

?characters. The i-th character of the string should be 1 if you appended the integer during the i-th query; otherwise, it should be 0.

---------------------------------------------------------

如果可以從數(shù)組的開頭刪除幾個（可能是零）元素并將所有這些元素以相同的順序插入到數(shù)組的后面，則數(shù)組 [a1,a2,…,ak] 被稱為漂亮的 結(jié)果數(shù)組按非降序排序的方式。

換句話說，如果存在一個整數(shù) i∈[0,k?1] 使得數(shù)組 [ai+1,ai+2,…,ak?1, ak,a1,a2,…,ai]

? 按非降序排序。

例如：

[3,7,7,9,2,3] 很漂亮：我們可以刪除前面的四個元素，然后以相同的順序?qū)⑺鼈儾迦氲胶竺?，我們就得到了?shù)組 [2,3,3,7,7,9 ]

，按非降序排序；

[1,2,3,4,5]很漂亮：我們可以刪除零個第一個元素并將它們插入到后面，我們就得到了數(shù)組[1,2,3,4,5]，它是按非排序的 降序;

[5,2,2,1] 并不漂亮。

請注意，任何由零個元素或一個元素組成的數(shù)組都是美麗的。

給定一個數(shù)組 a，它最初是空的。 您必須處理對其的 q 個查詢。 在第 i 次查詢期間，您將得到一個整數(shù) xi

，并且您必須執(zhí)行以下操作：

如果你可以將整數(shù) xi 附加到數(shù)組 a 的后面，以使數(shù)組 a 保持美觀，則必須附加它；否則，什么也不做。

每次查詢后，報告您是否附加了給定的整數(shù) xi

， 或不。

輸入

第一行包含一個整數(shù) t (1≤t≤104) — 測試用例的數(shù)量。

每個測試用例由兩行組成。 第一行包含一個整數(shù) q (1≤q≤2?105) — 查詢數(shù)。 第二行包含q

? 整數(shù) x1,x2,…,xq (0≤xi≤109)。

輸入的附加約束：所有測試用例的 q 總和不超過 2?105)。

輸出

對于每個測試用例，打印一個由 q 組成的字符串

? 人物。 如果在第 i 個查詢期間附加整數(shù)，則字符串的第 i 個字符應(yīng)為 1； 否則，它應(yīng)該是 0。

-----------------

相當(dāng)于一共存在兩種狀態(tài)，

1：一直是上升的趨勢的數(shù)組；（只要判斷新增的元素跟最近的元素的大小即可）

2：2個上升趨勢的數(shù)組；（要判斷新增的元素跟最近的元素，還要判斷跟第一個元素的大?。?/p>

這兩種狀態(tài)使用一個布爾變量處理；

下面是代碼：