#include<bits/stdc++.h>
using namespace std;




int main()
{
   
   
   
   
    long long t;cin>>t;
    
    
    
    while(t--)
        
    {
        
        
        
        
    long long n;cin>>n;
    
    bool lool=true;
    long long has[n+991];
    
    
    for(long long i=0;i<n;i++)
        ///in elements
        cin>>has[i];
        
set<long long> s;



    long long qwe=has[0];
    
    
    
    
    s.insert(has[0]);
    
    
    
    for(long long i=1;i<n;i++)
    {if(has[i]==qwe && 1==1)
            /// go on
            continue;
        
        
        
        else if(has[i]>qwe && 1==1)
            {auto lo=s.upper_bound(qwe);
            
            ///check if s 0
            if(lo==s.end())
                  
                  
                  
                  s.insert(has[i]);
            
            else
                /// recheck here
                {if(*lo<has[i])
                {lool=false;
                    break;}
                else
                    s.insert(has[i]);}}
                    
                    
                    /// other wise 2
                    
        else
            
            
            
            {auto lo=s.lower_bound(qwe);
            if(lo==s.begin()){
                s.insert(has[i]);}
                
                
           
           
            else
                
                
            
            
            {
                
                    
                lo--;
                if(*lo>has[i] && 1==1)
                    {lool=false;
                ///out
                    break;}
                
                
                
                else
                    
                    
                    s.insert(has[i]);}}
        qwe=has[i];}
        
        
        
        
        
    if(lool>0 && 1==1)
        cout<<"YES"<<endl;
    
    else
        
        
        cout<<"NO"<<endl;}

        
        
        
      return 0;  
        
    }
        
        /// Lool
        
        
        
        
        /*
 
#include<bits/stdc++.h>
 
using namespace std;
 
 
 
 
int main()
{
 
    int  t;cin>>t;
    while(t--)
    
    
        {
        
        
        
        
    long long n;cin>>n;
    
    vector<long long> has(n+991);
    set<long long>lol;
    
    
    
    
    for(long long i=0;i<n;i++)
        {cin>>has[i];
        lol.insert(has[i]);}
        
        
    queue<long long>jeme;
    
    
    for(long long i=1;i<n;i++)
    {for(long long j=0;j<i;j++)     {jeme.push(abs(has[i]-has[j]));}}
            
    while(!jeme.empty() && lol.size()<=300){
        long long lool=jeme.front();
        jeme.pop();
        
        
        if(lol.count(lool))
            continue;
        
        for(long long i=0;i<has.size();i++)
            jeme.push(abs(lool-has[i]));
            
            
        has.push_back(lool);
        lol.insert(lool);}
        
        
        
    if(lol.size()<=300)
        {cout<<"YES"<<endl;
        
        
        
        cout<<lol.size()<<endl;
        
        
        for(auto h1:lol)
            cout<<h1<<" ";
        
        cout<<endl;}
        
        
    else   cout<<"NO"<<endl;}
        
       
    return 0;
}
 
*/
        
        
        
        
        
        
        
        
        
        
    

### Prompt

Create a solution in cpp for the following problem:

Uh oh! Ray lost his array yet again! However, Omkar might be able to help because he thinks he has found the OmkArray of Ray's array. The OmkArray of an array a with elements a_1, a_2, …, a_{2k-1}, is the array b with elements b_1, b_2, …, b_{k} such that b_i is equal to the median of a_1, a_2, …, a_{2i-1} for all i. Omkar has found an array b of size n (1 ≤ n ≤ 2 ⋅ 10^5, -10^9 ≤ b_i ≤ 10^9). Given this array b, Ray wants to test Omkar's claim and see if b actually is an OmkArray of some array a. Can you help Ray?

The median of a set of numbers a_1, a_2, …, a_{2i-1} is the number c_{i} where c_{1}, c_{2}, …, c_{2i-1} represents a_1, a_2, …, a_{2i-1} sorted in nondecreasing order. 

Input

Each test contains multiple test cases. The first line contains a single integer t (1 ≤ t ≤ 10^4) — the number of test cases. Description of the test cases follows.

The first line of each test case contains an integer n (1 ≤ n ≤ 2 ⋅ 10^5) — the length of the array b.

The second line contains n integers b_1, b_2, …, b_n (-10^9 ≤ b_i ≤ 10^9) — the elements of b.

It is guaranteed the sum of n across all test cases does not exceed 2 ⋅ 10^5. 

Output

For each test case, output one line containing YES if there exists an array a such that b_i is the median of a_1, a_2, ..., a_{2i-1} for all i, and NO otherwise. The case of letters in YES and NO do not matter (so yEs and No will also be accepted).

Examples

Input


5
4
6 2 1 3
1
4
5
4 -8 5 6 -7
2
3 3
4
2 1 2 3


Output


NO
YES
NO
YES
YES


Input


5
8
-8 2 -6 -5 -4 3 3 2
7
1 1 3 1 0 -2 -1
7
6 12 8 6 2 6 10
6
5 1 2 3 6 7
5
1 3 4 3 0


Output


NO
YES
NO
NO
NO

Note

In the second case of the first sample, the array [4] will generate an OmkArray of [4], as the median of the first element is 4.

In the fourth case of the first sample, the array [3, 2, 5] will generate an OmkArray of [3, 3], as the median of 3 is 3 and the median of 2, 3, 5 is 3.

In the fifth case of the first sample, the array [2, 1, 0, 3, 4, 4, 3] will generate an OmkArray of [2, 1, 2, 3] as 

  * the median of 2 is 2 
  * the median of 0, 1, 2 is 1 
  * the median of 0, 1, 2, 3, 4 is 2 
  * and the median of 0, 1, 2, 3, 3, 4, 4 is 3. 



In the second case of the second sample, the array [1, 0, 4, 3, 5, -2, -2, -2, -4, -3, -4, -1, 5] will generate an OmkArray of [1, 1, 3, 1, 0, -2, -1], as 

  * the median of 1 is 1 
  * the median of 0, 1, 4 is 1 
  * the median of 0, 1, 3, 4, 5 is 3 
  * the median of -2, -2, 0, 1, 3, 4, 5 is 1 
  * the median of -4, -2, -2, -2, 0, 1, 3, 4, 5 is 0 
  * the median of -4, -4, -3, -2, -2, -2, 0, 1, 3, 4, 5 is -2 
  * and the median of -4, -4, -3, -2, -2, -2, -1, 0, 1, 3, 4, 5, 5 is -1 



For all cases where the answer is NO, it can be proven that it is impossible to find an array a such that b is the OmkArray of a.

### Response

```cpp
#include<bits/stdc++.h>
using namespace std;




int main()
{
   
   
   
   
    long long t;cin>>t;
    
    
    
    while(t--)
        
    {
        
        
        
        
    long long n;cin>>n;
    
    bool lool=true;
    long long has[n+991];
    
    
    for(long long i=0;i<n;i++)
        ///in elements
        cin>>has[i];
        
set<long long> s;



    long long qwe=has[0];
    
    
    
    
    s.insert(has[0]);
    
    
    
    for(long long i=1;i<n;i++)
    {if(has[i]==qwe && 1==1)
            /// go on
            continue;
        
        
        
        else if(has[i]>qwe && 1==1)
            {auto lo=s.upper_bound(qwe);
            
            ///check if s 0
            if(lo==s.end())
                  
                  
                  
                  s.insert(has[i]);
            
            else
                /// recheck here
                {if(*lo<has[i])
                {lool=false;
                    break;}
                else
                    s.insert(has[i]);}}
                    
                    
                    /// other wise 2
                    
        else
            
            
            
            {auto lo=s.lower_bound(qwe);
            if(lo==s.begin()){
                s.insert(has[i]);}
                
                
           
           
            else
                
                
            
            
            {
                
                    
                lo--;
                if(*lo>has[i] && 1==1)
                    {lool=false;
                ///out
                    break;}
                
                
                
                else
                    
                    
                    s.insert(has[i]);}}
        qwe=has[i];}
        
        
        
        
        
    if(lool>0 && 1==1)
        cout<<"YES"<<endl;
    
    else
        
        
        cout<<"NO"<<endl;}

        
        
        
      return 0;  
        
    }
        
        /// Lool
        
        
        
        
        /*
 
#include<bits/stdc++.h>
 
using namespace std;
 
 
 
 
int main()
{
 
    int  t;cin>>t;
    while(t--)
    
    
        {
        
        
        
        
    long long n;cin>>n;
    
    vector<long long> has(n+991);
    set<long long>lol;
    
    
    
    
    for(long long i=0;i<n;i++)
        {cin>>has[i];
        lol.insert(has[i]);}
        
        
    queue<long long>jeme;
    
    
    for(long long i=1;i<n;i++)
    {for(long long j=0;j<i;j++)     {jeme.push(abs(has[i]-has[j]));}}
            
    while(!jeme.empty() && lol.size()<=300){
        long long lool=jeme.front();
        jeme.pop();
        
        
        if(lol.count(lool))
            continue;
        
        for(long long i=0;i<has.size();i++)
            jeme.push(abs(lool-has[i]));
            
            
        has.push_back(lool);
        lol.insert(lool);}
        
        
        
    if(lol.size()<=300)
        {cout<<"YES"<<endl;
        
        
        
        cout<<lol.size()<<endl;
        
        
        for(auto h1:lol)
            cout<<h1<<" ";
        
        cout<<endl;}
        
        
    else   cout<<"NO"<<endl;}
        
       
    return 0;
}
 
*/
        
        
        
        
        
        
        
        
        
        
    

```