#ifdef LOCAL
#pragma warning(disable:4996)
#pragma warning(disable:4244)
#pragma warning(disable:4554)
#define gets gets_s

#endif
#include<map>
#include<set>
#include<list>
#include<cmath>
#include<stack>
#include<queue>
#include<cmath>
#include<vector>
#include<string>
#include<cctype>
#include<cstdio>
#include<bitset>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<iomanip>
#include<assert.h>
#define ll long long
#define cl(a,x) memset((a),(x),sizeof(a))
#define lson 2*i
#define rson 2*i+1
#define sf scanf
#define ull unsigned long long
#define lowbit(x) (x)&(-x)
#define pii pair<int,int>
#define pll pair<long long,long long>
#define pdd pair<double,double>
#define ti tree[i]
#define endl "\n"
#define debug(num) #num << "=" << num << " "
ll q_pow(ll x, ll n, ll mod) { ll ret = 1; while (n) { if (n & 1) ret = x * ret%mod; x = x * x%mod; n >>= 1; }return ret; }
ll __gcd(ll x, ll y) { if (!y) return x; return __gcd(y, x%y); }
ll getbit(ll now) { int cnt = 0; while (now) { cnt++; now -= lowbit(now); }return cnt; }
int dx[] = { -1,1,0,0 };//上下左右
int dy[] = { 0,0,-1,1 };//
using namespace std;
const ll maxn = 5e5 + 10;
const ll INF = 0x3f3f3f3f;
const ll IINF = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9;
const int mod = 1e9 + 7;
void add(ll &x, ll y) { x += y; if (x >= mod) x -= mod; }

struct BIT {
	int tree[maxn];
	int n;
	void insert(int pos, int val) {
		for (int i = pos; i <= n; i += lowbit(i))
			tree[i] += val;
	}
	ll query(int pos) {
		ll ret = 0;
		for (int i = pos; i >= 1; i -= lowbit(i))
			ret += tree[i];
		return ret;
	}
};
BIT tr;
int _hash[maxn], cnt;
int a[maxn];

void solve() {
	int n;
	cin >> n;
	cnt = 0;

	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		_hash[++cnt] = a[i];
	}
	sort(_hash + 1, _hash + cnt + 1);
	cnt = unique(_hash + 1, _hash + cnt + 1) - _hash - 1;
	int flag = 1;
	//cerr << debug(cnt) << endl;

	for (int i = 1; i <= n; i++) {
		a[i] = lower_bound(_hash + 1, _hash + cnt + 1, a[i]) - _hash;
	}

	tr.n = cnt;
	tr.insert(a[1], 1);

	for (int i = 2; i <= n; i++) {
		int x = max(a[i], a[i - 1]);
		int y = min(a[i], a[i - 1]);
		if (tr.query(x - 1) - tr.query(y) > 0) flag = 0;
		tr.insert(a[i], 1);
	}

	for (int i = 0; i <= tr.n; i++)
		tr.tree[i] = 0;
	if (flag == 0) cout << "NO" << endl;
	else cout << "YES" << endl;
}

signed main(int argc, char *argv[]) {
	if (argc == 2 && strcmp("-debug", argv[1]) == 0) {
		freopen("in.txt", "r", stdin);
		freopen("out.txt", "w", stdout);
	}

	cout << fixed << setprecision(20); ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	int t = 1;
	cin >> t;

	while (t--) {
		solve();
	}

	return 0;
}
### Prompt

Please formulate 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
#ifdef LOCAL
#pragma warning(disable:4996)
#pragma warning(disable:4244)
#pragma warning(disable:4554)
#define gets gets_s

#endif
#include<map>
#include<set>
#include<list>
#include<cmath>
#include<stack>
#include<queue>
#include<cmath>
#include<vector>
#include<string>
#include<cctype>
#include<cstdio>
#include<bitset>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<iomanip>
#include<assert.h>
#define ll long long
#define cl(a,x) memset((a),(x),sizeof(a))
#define lson 2*i
#define rson 2*i+1
#define sf scanf
#define ull unsigned long long
#define lowbit(x) (x)&(-x)
#define pii pair<int,int>
#define pll pair<long long,long long>
#define pdd pair<double,double>
#define ti tree[i]
#define endl "\n"
#define debug(num) #num << "=" << num << " "
ll q_pow(ll x, ll n, ll mod) { ll ret = 1; while (n) { if (n & 1) ret = x * ret%mod; x = x * x%mod; n >>= 1; }return ret; }
ll __gcd(ll x, ll y) { if (!y) return x; return __gcd(y, x%y); }
ll getbit(ll now) { int cnt = 0; while (now) { cnt++; now -= lowbit(now); }return cnt; }
int dx[] = { -1,1,0,0 };//上下左右
int dy[] = { 0,0,-1,1 };//
using namespace std;
const ll maxn = 5e5 + 10;
const ll INF = 0x3f3f3f3f;
const ll IINF = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9;
const int mod = 1e9 + 7;
void add(ll &x, ll y) { x += y; if (x >= mod) x -= mod; }

struct BIT {
	int tree[maxn];
	int n;
	void insert(int pos, int val) {
		for (int i = pos; i <= n; i += lowbit(i))
			tree[i] += val;
	}
	ll query(int pos) {
		ll ret = 0;
		for (int i = pos; i >= 1; i -= lowbit(i))
			ret += tree[i];
		return ret;
	}
};
BIT tr;
int _hash[maxn], cnt;
int a[maxn];

void solve() {
	int n;
	cin >> n;
	cnt = 0;

	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		_hash[++cnt] = a[i];
	}
	sort(_hash + 1, _hash + cnt + 1);
	cnt = unique(_hash + 1, _hash + cnt + 1) - _hash - 1;
	int flag = 1;
	//cerr << debug(cnt) << endl;

	for (int i = 1; i <= n; i++) {
		a[i] = lower_bound(_hash + 1, _hash + cnt + 1, a[i]) - _hash;
	}

	tr.n = cnt;
	tr.insert(a[1], 1);

	for (int i = 2; i <= n; i++) {
		int x = max(a[i], a[i - 1]);
		int y = min(a[i], a[i - 1]);
		if (tr.query(x - 1) - tr.query(y) > 0) flag = 0;
		tr.insert(a[i], 1);
	}

	for (int i = 0; i <= tr.n; i++)
		tr.tree[i] = 0;
	if (flag == 0) cout << "NO" << endl;
	else cout << "YES" << endl;
}

signed main(int argc, char *argv[]) {
	if (argc == 2 && strcmp("-debug", argv[1]) == 0) {
		freopen("in.txt", "r", stdin);
		freopen("out.txt", "w", stdout);
	}

	cout << fixed << setprecision(20); ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	int t = 1;
	cin >> t;

	while (t--) {
		solve();
	}

	return 0;
}
```