题目详情题解（0）讨论（0）提交记录（0）

CF1841B.Keep it Beautiful

普及/提高-

通过率：0%

AC君温馨提醒

该题目为【codeforces】题库的题目，您提交的代码将被提交至codeforces进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

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.

输入输出样例

  • 输入#1

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

    输出#1

    111110010
11111
11011

说明/提示

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 .
首页