Constructive Problem

o-Sakurajimamai-o / 2023-06-30 / 原文

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

The task is to find out whether

Recall that

Input

Each test contains multiple test cases. The first line contains the number of test cases

The first line of each test case contains a single integer

The second line of each test case contains

It is guaranteed that the sum

Output

For each test case, print "Yes" if you can increase

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.

Example

input

Copy

1 2 1

0 2 2 0

3 2 0 2

output

Copy

Yes
Yes
No
No

Note

In the first test case,

In the second test case,

It can be shown that in the third and fourth test cases it is impossible to perform an operation so that the value of

#include <bits/stdc++.h>
//#define int long long
using namespace std;
const int N=2e5+10,mod=1e9+7;
string s;
int n,t,a[N],f[N],res,num,ans,m;
bool vis[N];
int mex()//寻找mex
{
    unordered_map<int,int>g;
    for(int i=0;i<n;i++) g[a[i]]=1;
    for(int i=0;i<=n;i++)
        if(!g.count(i)) return i;
}
int main()
{
    std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>t;
    while(t--){
        cin>>n;
        for(int i=0;i<n;i++) cin>>a[i];
        num=mex();
        int l=-1,r=-1;
        for(int i=0;i<n;i++){//这一步是记录下来数组里k+1的左端点和右端点
            if(a[i]==num+1){
                if(l==-1) l=i;
                r=i;
            }
        }
        if(l==-1&&r==-1){//如果数组里面没有k+1,那么要判断
        //如果k>=n的话就不行,例如 0 1 2 3 ,k=4,那就不行,因为数不够,否则就可以
            if(num<n) cout<<"YES"<<endl;
            else cout<<"NO"<<endl;
            continue;
        }
        else{
            for(int i=l;i<=r;i++) a[i]=num;//改完之后再判断一次
            ans=mex();
            if(ans==num+1) cout<<"YES"<<endl;
            else cout<<"NO"<<endl;
        }
    }
    return 0;
}