元素消除

C. Element Extermination

time limit per test1 second
memory limit per test256 megabytes

You are given an array a of length n, which initially is a permutation of numbers from 1 to n. In one operation, you can choose an index i (1≤i<n) such that ai<ai+1, and remove either ai or ai+1 from the array (after the removal, the remaining parts are concatenated).

For example, if you have the array [1,3,2], you can choose i=1 (since a1=1<a2=3), then either remove a1 which gives the new array [3,2], or remove a2 which gives the new array [1,2].

Is it possible to make the length of this array equal to 1 with these operations?

Input
The first line contains a single integer t (1≤t≤2⋅104) — the number of test cases. The description of the test cases follows.

The first line of each test case contains a single integer n (2≤n≤3⋅105) — the length of the array.

The second line of each test case contains n integers a1, a2, ..., an (1≤ai≤n, ai are pairwise distinct) — elements of the array.

It is guaranteed that the sum of n over all test cases doesn't exceed 3⋅105.

Output
For each test case, output on a single line the word "YES" if it is possible to reduce the array to a single element using the aforementioned operation, or "NO" if it is impossible to do so.

Example
inputCopy
4
3
1 2 3
4
3 1 2 4
3
2 3 1
6
2 4 6 1 3 5
outputCopy
YES
YES
NO
YES
Note
For the first two test cases and the fourth test case, we can operate as follow (the bolded elements are the pair chosen for that operation):

[1,2,3]→[1,2]→[1]
[3,1,2,4]→[3,1,4]→[3,4]→[4]
[2,4,6,1,3,5]→[4,6,1,3,5]→[4,1,3,5]→[4,1,5]→[4,5]→[4]

题意：
给你一个1-n组成的序列，你可以对其中ai<ai+1的数对进行操作，把ai或者ai+1移除，最后判断能否只剩下一个数。

思路探索：
整个序列是由若干个顺序和逆序组成，从第一个元素开始，都是顺序或者都是逆序结果显而易见。我们将两个顺序或者逆序的组合作为研究对象，如果是先顺序再逆序，如果第一个元素比最后一个元素小，那么我们可以消到只剩下第一个元素，如果不是，那么还会余下一个逆序列，如果是先逆序再顺序，如果第一个元素比最后一个小我们可以消到只剩下第一个元素，如果不是，那么也还会余下一个逆序列，并且这样处理是最优的，因为只有最左边的元素最小，我们才能把更多消除的机会留给右边。如果进行不断的消除，最后a1到an也变成了两个顺序或逆序的组合，同样的我们可以运用这个结论
代码：

#include<iostream>
#include<algorithm>
#include<math.h>

using namespace std;

int main()
{
    int t,n,m,x,begin,end;
    cin>>t;
    while(t--)
    {
        cin>>n;
        for(int i=1;i<=n;i++)
        {
            cin>>x;
            if(i==1)
            begin=x;
            if(i==n)
            end=x;
        }
        if(begin<end)
        cout<<"YES";
        else 
        cout<<"NO";
        cout<<endl;
    }
    getchar();
    getchar();
}