
                        //    I solemnly swear that I am upto no good //

#include <bits/stdc++.h>
using namespace std;
#define sub             freopen("input.txt", "r", stdin);//freopen("output.txt", "w", stdout);
#define ll              long long
#define ld              long double
#define ttime           cerr << '\n'<<"Time (in s): " << double(clock() - clk) * 1.0 / CLOCKS_PER_SEC << '\n';
#define pb              push_back
#define unq(a)          sort(all(a));(a).resize(unique(all(a)) - (a).begin())
#define sz(x)           (int)((x).size())
#define input(arr,n)    for(ll i1=0;i1<n;i1++ )cin>>arr[i1]
#define fast            ios_base::sync_with_stdio(false);cin.tie(0);
#define all(x)          (x).begin(),(x).end()
#define rep(i,a,b)      for(ll i=a;i<b;i++)
#define pr(x)           cout << #x " = " << (x) << "\n"
#define mp              make_pair
#define ff              first
#define ss              second
#define YY              cout<<"Yes"<<endl
#define NN              cout<<"No"<<endl
#define ppc             __builtin_popcount
#define ppcll           __builtin_popcountll

const long long INF=1e18;
const long long A=200005;
const long long mod=1000000007;                    // 2971215073, 1000050131, 433494437

#define endl "\n"
// #define int ll

typedef pair<ll,ll> pairll;
typedef map<ll,ll>  mapll;
typedef map<char,ll> mapch;
bool comp(ll a,ll b){
    return a>b;
}

ll n,k,tt=1;
vector<vector<ll> > dp(A, vector<ll> (3)); // only left, only right, left and right
void solve(){
    //string s,t;
    // ll m,q,x,y,ans=0;
    cin>>n; 
    std::vector<ll> ar(n);
    input(ar,n);

    rep(i,0,n)dp[i][0]=dp[i][1]=dp[i][2]=0;

    dp[0][0]=-INF;
    dp[0][1]=INF;


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

        if(ar[i]>ar[i-1]){
            if(ar[i]==dp[i-1][1]){
                dp[i][0]=ar[i-1];
                for(int j=i-2;j>=0;j--)if(dp[j][1]>ar[i]){
                                dp[i][1]=dp[j][1];break;}
                continue;
            }
            dp[i][0]=ar[i-1];
            if(dp[i-1][1]>=ar[i])dp[i][1]=dp[i-1][1];
            else {
                NN;
                return;
            }
        }
        else if(ar[i]<ar[i-1]){
            if(ar[i]==dp[i-1][0]){
                dp[i][1]=ar[i-1];
                for(int j=i-2;j>=0;j--)if(dp[j][0]<ar[i]){
                                dp[i][0]=dp[j][0];break;}
                continue;
            }
            dp[i][1]=ar[i-1];
            if(dp[i-1][0]<=ar[i])dp[i][0]=dp[i-1][0];
            else {
                NN;
                return;
            }
        }
        else {
            dp[i]=dp[i-1];
        }
                // cout<<ar[i]<<" "<<dp[i][0]<<" "<<dp[i][1]<<endl;

    }

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

    YY;

    

    

}

signed main(){ 
    // sub;    
    fast;
    // pre();
    // clock_t clk = clock();
    ll t=1;
    cin>>t;
    while(t--){
        solve();
    }
    // ttime;
    return 0;
}        

                                // Mischief Managed //   
                                         
### Prompt

Generate a CPP solution to 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

                        //    I solemnly swear that I am upto no good //

#include <bits/stdc++.h>
using namespace std;
#define sub             freopen("input.txt", "r", stdin);//freopen("output.txt", "w", stdout);
#define ll              long long
#define ld              long double
#define ttime           cerr << '\n'<<"Time (in s): " << double(clock() - clk) * 1.0 / CLOCKS_PER_SEC << '\n';
#define pb              push_back
#define unq(a)          sort(all(a));(a).resize(unique(all(a)) - (a).begin())
#define sz(x)           (int)((x).size())
#define input(arr,n)    for(ll i1=0;i1<n;i1++ )cin>>arr[i1]
#define fast            ios_base::sync_with_stdio(false);cin.tie(0);
#define all(x)          (x).begin(),(x).end()
#define rep(i,a,b)      for(ll i=a;i<b;i++)
#define pr(x)           cout << #x " = " << (x) << "\n"
#define mp              make_pair
#define ff              first
#define ss              second
#define YY              cout<<"Yes"<<endl
#define NN              cout<<"No"<<endl
#define ppc             __builtin_popcount
#define ppcll           __builtin_popcountll

const long long INF=1e18;
const long long A=200005;
const long long mod=1000000007;                    // 2971215073, 1000050131, 433494437

#define endl "\n"
// #define int ll

typedef pair<ll,ll> pairll;
typedef map<ll,ll>  mapll;
typedef map<char,ll> mapch;
bool comp(ll a,ll b){
    return a>b;
}

ll n,k,tt=1;
vector<vector<ll> > dp(A, vector<ll> (3)); // only left, only right, left and right
void solve(){
    //string s,t;
    // ll m,q,x,y,ans=0;
    cin>>n; 
    std::vector<ll> ar(n);
    input(ar,n);

    rep(i,0,n)dp[i][0]=dp[i][1]=dp[i][2]=0;

    dp[0][0]=-INF;
    dp[0][1]=INF;


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

        if(ar[i]>ar[i-1]){
            if(ar[i]==dp[i-1][1]){
                dp[i][0]=ar[i-1];
                for(int j=i-2;j>=0;j--)if(dp[j][1]>ar[i]){
                                dp[i][1]=dp[j][1];break;}
                continue;
            }
            dp[i][0]=ar[i-1];
            if(dp[i-1][1]>=ar[i])dp[i][1]=dp[i-1][1];
            else {
                NN;
                return;
            }
        }
        else if(ar[i]<ar[i-1]){
            if(ar[i]==dp[i-1][0]){
                dp[i][1]=ar[i-1];
                for(int j=i-2;j>=0;j--)if(dp[j][0]<ar[i]){
                                dp[i][0]=dp[j][0];break;}
                continue;
            }
            dp[i][1]=ar[i-1];
            if(dp[i-1][0]<=ar[i])dp[i][0]=dp[i-1][0];
            else {
                NN;
                return;
            }
        }
        else {
            dp[i]=dp[i-1];
        }
                // cout<<ar[i]<<" "<<dp[i][0]<<" "<<dp[i][1]<<endl;

    }

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

    YY;

    

    

}

signed main(){ 
    // sub;    
    fast;
    // pre();
    // clock_t clk = clock();
    ll t=1;
    cin>>t;
    while(t--){
        solve();
    }
    // ttime;
    return 0;
}        

                                // Mischief Managed //   
                                         
```