//REMEMBERING THE PAST , CAN AVOID REPEAT THE SAME 
#include<bits/stdc++.h>
using namespace std;
#define mod 1000000007
#define inf 10000000000000000
typedef long long ll;
#define mp make_pair
#define f first 
#define s second
// DP o Trees::http://cfrp.azurewebsites.net/blog/entry/20935
ll GCD(ll a,ll b){
    ll maxi=max(a,b);
    ll mini=min(a,b);
    while(maxi && mini){
        ll t=mini;
        mini=maxi%mini;
        maxi=t; 
    }
    return max(maxi,mini);
}
ll power(ll x,ll y){
    ll res=1;
    while (y){
        if (y & 1){
            res=(res*x)%mod; 
        }
        x=(x*x)%mod;
        y=y>>1;
    }
    return res%mod;
}
ll ncr(ll x, ll y){
 	ll ans=1;
 	y=(y > x-y? x-y: y);
 	for(ll i=0; i<y; i++){
 		ans=(ans*(x-i))%mod;
 		ans=(ans*power(i+1,mod-2))%mod;
 		ans=ans%mod;
 	}
 	return ans;
 }
int lower_bound(vector<int> &v,int x){
    int l=0,n=v.size(),r=n-1,mid;
    int ans=0;  
    while (l<=r){ 
        mid=l+(r-l)/2;
        if (v[mid]>=x){
            ans=mid;
            r=mid-1;
        }
        else{
            l=mid+1;
        }
    } 
    return ans;
}
int upper_bound(vector<int> &v,int x){
    int l=0,n=v.size(),r=n-1,mid;
    int ans=n; 
    while (l<=r){
        mid=l+(r-l)/2;
        if (v[mid]>x){
            ans=mid;
            r=mid-1;
        }
        else{
            l=mid+1;
        }
    }
    return ans;
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int t;
	cin>>t;
	while(t--){
		int n,x;
		cin>>n;
		set<int> nums;
		nums.insert(-1);
		int prev=-1;
		bool flag=true;
		for(int i=0;i<n;i++){
			// cout<<flag<<" ";
			cin>>x;
			if(flag){
				nums.insert(x);
				auto it1=nums.lower_bound(prev);
				auto it2=nums.lower_bound(x);
				if(it1==it2 || ++it1==it2 || --(--it1)==it2){
					flag=true;
				}
				else{
					flag=false;
				}
			}
			if(i==0){
				auto it=nums.lower_bound(-1);
				nums.erase(it);
			}
			prev=x;
			nums.insert(x);
		}
		if(flag){
			cout<<"YES\n";
		}
		else{
			cout<<"NO\n";
		}
	}
	return 0;
}
### Prompt

Develop a solution in cpp to the problem described below:

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
//REMEMBERING THE PAST , CAN AVOID REPEAT THE SAME 
#include<bits/stdc++.h>
using namespace std;
#define mod 1000000007
#define inf 10000000000000000
typedef long long ll;
#define mp make_pair
#define f first 
#define s second
// DP o Trees::http://cfrp.azurewebsites.net/blog/entry/20935
ll GCD(ll a,ll b){
    ll maxi=max(a,b);
    ll mini=min(a,b);
    while(maxi && mini){
        ll t=mini;
        mini=maxi%mini;
        maxi=t; 
    }
    return max(maxi,mini);
}
ll power(ll x,ll y){
    ll res=1;
    while (y){
        if (y & 1){
            res=(res*x)%mod; 
        }
        x=(x*x)%mod;
        y=y>>1;
    }
    return res%mod;
}
ll ncr(ll x, ll y){
 	ll ans=1;
 	y=(y > x-y? x-y: y);
 	for(ll i=0; i<y; i++){
 		ans=(ans*(x-i))%mod;
 		ans=(ans*power(i+1,mod-2))%mod;
 		ans=ans%mod;
 	}
 	return ans;
 }
int lower_bound(vector<int> &v,int x){
    int l=0,n=v.size(),r=n-1,mid;
    int ans=0;  
    while (l<=r){ 
        mid=l+(r-l)/2;
        if (v[mid]>=x){
            ans=mid;
            r=mid-1;
        }
        else{
            l=mid+1;
        }
    } 
    return ans;
}
int upper_bound(vector<int> &v,int x){
    int l=0,n=v.size(),r=n-1,mid;
    int ans=n; 
    while (l<=r){
        mid=l+(r-l)/2;
        if (v[mid]>x){
            ans=mid;
            r=mid-1;
        }
        else{
            l=mid+1;
        }
    }
    return ans;
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int t;
	cin>>t;
	while(t--){
		int n,x;
		cin>>n;
		set<int> nums;
		nums.insert(-1);
		int prev=-1;
		bool flag=true;
		for(int i=0;i<n;i++){
			// cout<<flag<<" ";
			cin>>x;
			if(flag){
				nums.insert(x);
				auto it1=nums.lower_bound(prev);
				auto it2=nums.lower_bound(x);
				if(it1==it2 || ++it1==it2 || --(--it1)==it2){
					flag=true;
				}
				else{
					flag=false;
				}
			}
			if(i==0){
				auto it=nums.lower_bound(-1);
				nums.erase(it);
			}
			prev=x;
			nums.insert(x);
		}
		if(flag){
			cout<<"YES\n";
		}
		else{
			cout<<"NO\n";
		}
	}
	return 0;
}
```