This editorial is not provided by Editorialist but so for knowledge.

ERASE BUT ALL ONE

The question requires some observations that can help you to implement it easily. The question asks that given you a permutation, You can do the following operation

- Select two distinct indexes i and j such that A[i] < A[j] , then you can remove any one of them and rest array is then concatenated.

You need to use the above operation and tell whether it is possible to delete exactly N-1 elements from the array such that only 1 element is left in the array.

The first and most easy observation is to see that whenever there is a case such that the first element of array is N or last element of array is 1 we can never be able to delete N-1 elements from it as N cannot be deleted in the former case and 1 cannot be deleted in the second case thus there would be one more element atleast left in the array making a total of 2 elements thus not possible. The next observation is just a more generalisation of above small observation.

CLAIM : If the MEX(Minimum Excludant) of the last i numbers is i+1, where 1<= i+1 <= N, then we cannot satisfy the above asked question. Here MEX has been considered to start from 1 and not from 0.

PROOF : Let us take an example for N = 6

Suppose the permutation is = 4 5 3 6 1 2 . In this case we can delete 4 by using 6, 5 by using 6 and then we are left with 3 6 1 2 . It is clear that deleting either 3 or 6 will result in something either 3 1 2 or 6 1 2 for which we cannot do any operation to fulfiil above So the key observations says that if (large numbers are grouped on one side) and (small numbers are grouped on other side) then it would not be possible to do above statement. But now how do we define small and large numbers so here comes MEX use. If I take example given above and start iterating from back of the array then at at index 4 (i.e 1) we get MEX as 3 which is just (2+1) here 2 is the number of elements we have traversed so we cannot do above operations to convert.

For confirmity let us take an example where its possible to convert

for N = 5, 4 3 1 2 5 here at each point MEX condition is not satisified. Let me show you a dry run

. At idx = 4, element = 5 , MEX = 1 , (1+1) = 2 not equal to MEX

At idx = 3 , element = 2 , MEX = 1, (2+1) = 3 not equal to MEX

At idx = 2 , element = 1, MEX = 3, (3+1) = 4 not equal to MEX

At idx = 1, element = 3, MEX = 4, (4+1) = 5 not equal to MEX

At idx = 0 , element = 4, (here we have that our permutation has run out of numbers as MEX = 6 which is not a part of our permuation as N = 5) so here although MEX = 6 is equal to (5+1) but at the same it must be a part of out permutation. So we get that our answer is possible.

Now to find MEX I have used set data structure in C++ STL by which we can easily implement above solution. As retrieval time in set is log(N) so overall time complexity of above approach is

N*log(N) which well fits in time complexity. There are much intelligent implementation for MEX that take O(N) time. You can check them out too.

## Solution

```
#include<bits/stdc++.h>
using namespace std;
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t;
cin>>t;
while(t--){
int n;
cin>>n;
vector<int>A(n);
for(int i = 0; i<n; i++){
cin>>A[i];
}
set<int>mex;
for(int i = 1; i<=n; i++){
mex.insert(i);
}
int p = 0;
bool check = true;
for(int i = n-1; i>=0; i--){
int m = 0;
p++;
mex.erase(A[i]);
m = *(mex.begin());
if(p+1==m){
check = false;
break;
}
}
cout<<(check == true ? "YES\n" : "NO\n");
}
return 0;
}
```

Solution by : cody_36