#P1841B. Keep it Beautiful

Keep it Beautiful

No submission language available for this problem.

Description

The array [a1,a2,…,ak][a_1, a_2, \dots, a_k] 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][a_1, a_2, \dots, a_k] is beautiful if there exists an integer i∈[0,k−1]i \in [0, k-1] such that the array [ai+1,ai+2,…,ak−1,ak,a1,a2,…,ai][a_{i+1}, a_{i+2}, \dots, a_{k-1}, a_k, a_1, a_2, \dots, a_i] is sorted in non-descending order.

For example:

  • [3,7,7,9,2,3][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][2, 3, 3, 7, 7, 9], which is sorted in non-descending order;
  • [1,2,3,4,5][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][1, 2, 3, 4, 5], which is sorted in non-descending order;
  • [5,2,2,1][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 aa, which is initially empty. You have to process qq queries to it. During the ii-th query, you will be given one integer xix_i, and you have to do the following:

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

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

The first line contains one integer tt (1≤t≤1041 \le t \le 10^4) — the number of test cases.

Each test case consists of two lines. The first line contains one integer qq (1≤q≤2⋅1051 \le q \le 2 \cdot 10^5) — the number of queries. The second line contains qq integers x1,x2,…,xqx_1, x_2, \dots, x_q (0≤xi≤1090 \le x_i \le 10^9).

Additional constraint on the input: the sum of qq over all test cases does not exceed 2⋅1052 \cdot 10^5).

For each test case, print one string consisting of exactly qq characters. The ii-th character of the string should be 1 if you appended the integer during the ii-th query; otherwise, it should be 0.

Input

The first line contains one integer tt (1≤t≤1041 \le t \le 10^4) — the number of test cases.

Each test case consists of two lines. The first line contains one integer qq (1≤q≤2⋅1051 \le q \le 2 \cdot 10^5) — the number of queries. The second line contains qq integers x1,x2,…,xqx_1, x_2, \dots, x_q (0≤xi≤1090 \le x_i \le 10^9).

Additional constraint on the input: the sum of qq over all test cases does not exceed 2⋅1052 \cdot 10^5).

Output

For each test case, print one string consisting of exactly qq characters. The ii-th character of the string should be 1 if you appended the integer during the ii-th query; otherwise, it should be 0.

Sample Input 1

3
9
3 7 7 9 2 4 6 3 4
5
1 1 1 1 1
5
3 2 1 2 3
Copy

Sample Output 1

111110010
11111
11011
Copy

Note

Consider the first test case of the example. Initially, the array is [][].

  • trying to append an integer 33. The array [3][3] is beautiful, so we append 33;
  • trying to append an integer 77. The array [3,7][3, 7] is beautiful, so we append 77;
  • trying to append an integer 77. The array [3,7,7][3, 7, 7] is beautiful, so we append 77;
  • trying to append an integer 99. The array [3,7,7,9][3, 7, 7, 9] is beautiful, so we append 99;
  • trying to append an integer 22. The array [3,7,7,9,2][3, 7, 7, 9, 2] is beautiful, so we append 22;
  • trying to append an integer 44. The array [3,7,7,9,2,4][3, 7, 7, 9, 2, 4] is not beautiful, so we don't append 44;
  • trying to append an integer 66. The array [3,7,7,9,2,6][3, 7, 7, 9, 2, 6] is not beautiful, so we don't append 66;
  • trying to append an integer 33. The array [3,7,7,9,2,3][3, 7, 7, 9, 2, 3] is beautiful, so we append 33;
  • trying to append an integer 44. The array [3,7,7,9,2,3,4][3, 7, 7, 9, 2, 3, 4] is not beautiful, so we don't append 44.
  1. About
  2. Contact Us
  3. Privacy
  4. Terms of Service
  5. Copyright Complaint
  6. Language
  7. Legacy mode
  8. Theme
  2. 蜀ICP备2021003932号-1
  3. Worker 0, 32ms
  4. Powered by Hydro v4.19.1 Community