CF1819A.Constructive Problem
普及/提高-
通过率:0%
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
As you know, any problem that does not require the use of complex data structures is considered constructive. You are offered to solve one of such problems.
You are given an array a of n non-negative integers. You are allowed to perform the following operation exactly once: choose some non-empty subsegment al,al+1,…,ar of the array a and a non-negative integer k , and assign value k to all elements of the array on the chosen subsegment.
The task is to find out whether MEX(a) can be increased by exactly one by performing such an operation. In other words, if before the operation MEX(a)=m held, then after the operation it must hold that MEX(a)=m+1 .
Recall that MEX of a set of integers c1,c2,…,ck is defined as the smallest non-negative integer x which does not occur in the set c .
输入格式
Each test contains multiple test cases. The first line contains the number of test cases t ( 1≤t≤50000 ) — the number of test cases. The description of the test cases follows.
The first line of each test case contains a single integer n ( 1≤n≤200000 ) — the number of elements of array a .
The second line of each test case contains n integers a1,a2,…,an ( 0≤ai≤109 ) — elements of array a .
It is guaranteed that the sum n over all test cases does not exceed 200000 .
输出格式
For each test case, print "Yes" if you can increase MEX(a) by exactly one by performing the operation from the statement exactly once, otherwise print "No".
You can output the answer in any case (upper or lower). For example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as positive responses.
输入输出样例
输入#1
4 3 1 2 1 4 0 2 2 0 4 3 2 0 2 1 0
输出#1
Yes Yes No No
说明/提示
In the first test case, MEX(a)=0 . If you set all elements of a to 0 , then MEX of the resulting array will be 1 , and thus will increase by one.
In the second test case, MEX(a)=1 . If we assign a value of 1 to the elements of a on a subsegment from 2 to 3 , we get an array [0,1,1,0] for which MEX is 2 , and thus is increased by one compared to the original.
It can be shown that in the third and fourth test cases it is impossible to perform an operation so that the value of MEX(a) increases by exactly one.