Erase All But One:

You are given a permutation P$P$ of length N$N$. You can perform the following operation on P$P$:

• Choose any i$i$ and j$j$ such that i<j$i<j$ and Pi<Pj$P_i<P_j$, and remove exactly one of them from the array. After removing, the remaining parts of the array are concatenated.

Find out if it is possible to apply the given operation any number of times such that only one element remains in the array.

Note: A permutation of length N$N$ is an array where every element from 1$1$ to N$N$ occurs exactly once.

Input Format

• The first line contains T$T$ - the number of test cases. Then the test cases follow.
• The first line of each test case contains N$N$ - the length of the permutation P$P$.
• The second line of each test case contains N$N$ space-separated integers P1,P2,…,PN$P_1,P_2,\dots ,P_N$ - elements of the permutation.

Output Format

For each test case, output YES if it is possible to reduce the array to a single element using the given operation. Otherwise, output NO.

You may print each character of the string in uppercase or lowercase (for example, the strings yEs, yes, Yes and YES will all be treated as identical).

Constraints

• 1≤T≤3⋅105$1\le T\le 3\cdot {10}^5$
• 1≤N≤3⋅105$1\le N\le 3\cdot {10}^5$
• 1≤Pi≤N$1\le P_i\le N$
• P1,P2,…,PN$P_1,P_2,\dots ,P_N$ form a permutation of length N$N$
• ∑N$\sum N$ over all test cases is at most 3⋅105$3\cdot {10}^5$

Sample Input 1 

3
4
3 1 2 4
3
2 3 1
6
5 2 3 6 1 4

Sample Output 1 

YES
NO
YES

Explanation

• Test case 1$1$: We can apply operations as follows (the bolded elements are the pair chosen for that operation): [3,1,2,4]→[1,2,4]→[2,4]→[4]$[\mathbf{\text{3}},\text{1},\text{2},\mathbf{\text{4}}]\to [\mathbf{\text{1}},\text{2},\mathbf{\text{4}}]\to [\mathbf{\text{2}},\mathbf{\text{4}}]\to [\text{4}]$
• Test case 2$2$: It can be shown that it is not possible to remove all elements except one element from the array.
• Test case 3$3$: We can apply operations as follows: [5,2,3,6,1,4]→[2,3,6,1,4]→[2,3,1,4]→[3,1,4]→[1,4]→[4]

SOLUTION:

#include <bits/stdc++.h>

using namespace std;

void testcase(){

    int n;

    cin >> n;

    vector<int> v(n) , ind(n+1);

    for(int i=0 ; i<n ; i++){

        cin >> v[i];

        ind[v[i]] = i;

    }

    

    int sm = ind[1];

    vector<bool> vis(n+1 , 0);

    vis[1] = 1;

    stack<int> st;

    for(int i=2 ; i<=n ; i++){

        if(ind[i] > sm){

            vis[i] = 1;

            while(!st.empty()){

                int top = st.top();

                sm = min(sm , ind[top]);

                vis[top] = 1;

                st.pop();

            }

        }

        else st.push(i);

    }

    

    for(int i=1 ; i<=n ; i++){

        if(!vis[i]){

            cout << "NO" << endl;

            return;

        }

    }

    

    cout << "YES" << endl;

}

int main() {

// your code goes here

int tt;

cin >> tt;

while(tt--){

    testcase();

}

return 0;

}