#include <bits/stdc++.h>
using namespace std;
#define li long long int
#define le long double5
#define mod 1000000007
#define maxe 100006
vector<bool> pu(maxe + 1, false);
vector<li> pr;
vector<li> prevprime(maxe + 1, 1);
class dop
{public:
li n,p,q,r,m,o,c,d;
string s,v,u;
vector<li> a;
    void get();
};
void seive()
{
    for (li i = 2; (i) <= maxe; i++)
    {
        if (!pu[i])
        {
            prevprime[i] = i;
            for (li j = (2 * i); j <= maxe; j += i)
            {
                if (!pu[j])
                {
                    prevprime[j] = i;
                }
                pu[j] = true;
            }
            pr.push_back(i);
        }
    }
}
li power(li x, li n)
{
    li res = 1;
    while (n > 0)
    {
        if (n & 1)
        {
            res = ((res % mod) * (x % mod)) % mod;
        }
        n = n >> 1;
        x = ((x % mod) * (x % mod)) % mod;
    }
    return res;
}
li inv(li x)
{
    return power(x, mod - 2);
}
void factor(li x)
{
    while (x != 1)
    {
        li div = prevprime[x];

        while (prevprime[x] == div)
        {
            x /= div;
        }
    }
}
li gcd(li a, li b)
{
    if (a == 0)
    {
        return b;
    }
    return gcd(b % a, a);
}
void dop::get()
{cin>>n;
for(li i=0;i<n;i++){cin>>p;a.push_back(p);}
set<li> s;
s.insert(a[0]);
for(li i=1;i<n;i++){p=a[i-1];q=a[i];
if(q>p){auto itr=s.find(p);
auto ptr=next(itr);
if(ptr==s.end()){s.insert(q);continue;}
r=*ptr;if(r<q){cout<<"NO"<<endl;return ;}s.insert(q);}

if(q<p){auto itr=s.find(p);
if(itr==s.begin()){s.insert(q);continue;}auto ptr=prev(itr);
r=*ptr;
if(r>q){cout<<"NO"<<endl;return ;}s.insert(q);}s.insert(q);}

cout<<"YES"<<endl;

}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
#ifndef ONLINE_JUDGE
    // for getting input from input.txt
    freopen("input.txt", "r", stdin);
    // for writing output to output.txt
    freopen("output.txt", "w", stdout);
#endif
    li t = 1;
    cin >> t;
    dop obj[t];
    // seive();
    for (li i = 0; i < t; i++)
    {
        obj[i].get();
    }
    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
#include <bits/stdc++.h>
using namespace std;
#define li long long int
#define le long double5
#define mod 1000000007
#define maxe 100006
vector<bool> pu(maxe + 1, false);
vector<li> pr;
vector<li> prevprime(maxe + 1, 1);
class dop
{public:
li n,p,q,r,m,o,c,d;
string s,v,u;
vector<li> a;
    void get();
};
void seive()
{
    for (li i = 2; (i) <= maxe; i++)
    {
        if (!pu[i])
        {
            prevprime[i] = i;
            for (li j = (2 * i); j <= maxe; j += i)
            {
                if (!pu[j])
                {
                    prevprime[j] = i;
                }
                pu[j] = true;
            }
            pr.push_back(i);
        }
    }
}
li power(li x, li n)
{
    li res = 1;
    while (n > 0)
    {
        if (n & 1)
        {
            res = ((res % mod) * (x % mod)) % mod;
        }
        n = n >> 1;
        x = ((x % mod) * (x % mod)) % mod;
    }
    return res;
}
li inv(li x)
{
    return power(x, mod - 2);
}
void factor(li x)
{
    while (x != 1)
    {
        li div = prevprime[x];

        while (prevprime[x] == div)
        {
            x /= div;
        }
    }
}
li gcd(li a, li b)
{
    if (a == 0)
    {
        return b;
    }
    return gcd(b % a, a);
}
void dop::get()
{cin>>n;
for(li i=0;i<n;i++){cin>>p;a.push_back(p);}
set<li> s;
s.insert(a[0]);
for(li i=1;i<n;i++){p=a[i-1];q=a[i];
if(q>p){auto itr=s.find(p);
auto ptr=next(itr);
if(ptr==s.end()){s.insert(q);continue;}
r=*ptr;if(r<q){cout<<"NO"<<endl;return ;}s.insert(q);}

if(q<p){auto itr=s.find(p);
if(itr==s.begin()){s.insert(q);continue;}auto ptr=prev(itr);
r=*ptr;
if(r>q){cout<<"NO"<<endl;return ;}s.insert(q);}s.insert(q);}

cout<<"YES"<<endl;

}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
#ifndef ONLINE_JUDGE
    // for getting input from input.txt
    freopen("input.txt", "r", stdin);
    // for writing output to output.txt
    freopen("output.txt", "w", stdout);
#endif
    li t = 1;
    cin >> t;
    dop obj[t];
    // seive();
    for (li i = 0; i < t; i++)
    {
        obj[i].get();
    }
    return 0;
}
```