#include<bits/stdc++.h>
//#include <ext/pb_ds/;assoc_container.hpp>
//using namespace __gnu_pbds
using namespace std;
# define lint           long long 
#define lint             long long
#define pb              push_back
#define mp              make_pair
#define pii             pair<lint,lint>
#define vi              vector<int>
#define mii             map<int,int>
#define pqb             priority_queue<int>
#define pqs             priority_queue<int,vi,greater<int> >
#define setbits(x)      __builtin_popcountlint(x)
#define zrobits(x)      __builtin_ctzlint(x)
#define mod             1000000007
#define inf             1e18
#define ps(x,y)         fixed<<setprecision(y)<<x
#define mk(arr,n,type)  type *arr=new type[n];
#define t(x)            int x=1; cin>>x; while(x--)
#define fori(i,n)        for(lint i=0;i<n;i++)
#define fo(k,i,n)        for(lint i=k;i<n;i++)
 
void c_p_c()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
}
 
lint calc(int a,int b)
{
    if(a%b==0)
        return a/b;
    else
        return a/b +1;
}
 
unsigned long long power(unsigned long long x,
                                  int y, int p)
{
    unsigned long long res = 1; // Initialize result
 
    x = x % p; // Update x if it is more than or
    // equal to p
 
    while (y > 0)
    {
     
        // If y is odd, multiply x with result
        if (y & 1)
            res = (res * x) % p;
 
        // y must be even now
        y = y >> 1; // y = y/2
        x = (x * x) % p;
    }
    return res;
}
 
// Returns n^(-1) mod p
unsigned long long modInverse(unsigned long long n, 
                                            int p)
{
    return power(n, p - 2, p);
}
 
// Returns nCr % p using Fermat's little
// theorem.
long long fac[100001];
 
void solve()
{
    
fac[0] = 1;
    for (int i = 1; i <= 100000; i++)
        fac[i] = (fac[i - 1] * i) % mod;
}
 
unsigned long long nCrModPFermat(unsigned long long n,
                                 int r, int p)
{
    // If n<r, then nCr should return 0
    if (n < r)
        return 0;
    // Base case
    if (r == 0)
        return 1;
 
    // Fill factorial array so that we
    // can find all factorial of r, n
    // and n-r
 
    return (fac[n] * modInverse(fac[r], p) % p
            * modInverse(fac[n - r], p) % p)
           % p;
}



int main()
{
  c_p_c();
      
      t(x)
      {
        
        lint n;
        cin>>n;
        lint arr[n];
        fori(i,n)
        {
            cin>>arr[i];
        }

        set<lint> s;
        s.insert(arr[0]);
        bool f=true;

        for(int i=1;i<n;i++)
        {
            int a=arr[i-1];

            if(a>arr[i])
            {
                auto itr=s.lower_bound(a);

                if(itr!=s.begin() && *(--itr)>arr[i])
                {
                    f=false;
                    break;
                }
            }
            else if(a<arr[i])
            {
                 auto itr=s.upper_bound(a);

                 if(itr!=s.end() && *itr<arr[i])
                 {
                    f=false;
                    break;
                 }
            }

            s.insert(arr[i]);
        }

        if(f)
            cout<<"YES"<<endl;
        else
            cout<<"NO"<<endl;
      
      }

  return 0;
    
}
### 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
#include<bits/stdc++.h>
//#include <ext/pb_ds/;assoc_container.hpp>
//using namespace __gnu_pbds
using namespace std;
# define lint           long long 
#define lint             long long
#define pb              push_back
#define mp              make_pair
#define pii             pair<lint,lint>
#define vi              vector<int>
#define mii             map<int,int>
#define pqb             priority_queue<int>
#define pqs             priority_queue<int,vi,greater<int> >
#define setbits(x)      __builtin_popcountlint(x)
#define zrobits(x)      __builtin_ctzlint(x)
#define mod             1000000007
#define inf             1e18
#define ps(x,y)         fixed<<setprecision(y)<<x
#define mk(arr,n,type)  type *arr=new type[n];
#define t(x)            int x=1; cin>>x; while(x--)
#define fori(i,n)        for(lint i=0;i<n;i++)
#define fo(k,i,n)        for(lint i=k;i<n;i++)
 
void c_p_c()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
}
 
lint calc(int a,int b)
{
    if(a%b==0)
        return a/b;
    else
        return a/b +1;
}
 
unsigned long long power(unsigned long long x,
                                  int y, int p)
{
    unsigned long long res = 1; // Initialize result
 
    x = x % p; // Update x if it is more than or
    // equal to p
 
    while (y > 0)
    {
     
        // If y is odd, multiply x with result
        if (y & 1)
            res = (res * x) % p;
 
        // y must be even now
        y = y >> 1; // y = y/2
        x = (x * x) % p;
    }
    return res;
}
 
// Returns n^(-1) mod p
unsigned long long modInverse(unsigned long long n, 
                                            int p)
{
    return power(n, p - 2, p);
}
 
// Returns nCr % p using Fermat's little
// theorem.
long long fac[100001];
 
void solve()
{
    
fac[0] = 1;
    for (int i = 1; i <= 100000; i++)
        fac[i] = (fac[i - 1] * i) % mod;
}
 
unsigned long long nCrModPFermat(unsigned long long n,
                                 int r, int p)
{
    // If n<r, then nCr should return 0
    if (n < r)
        return 0;
    // Base case
    if (r == 0)
        return 1;
 
    // Fill factorial array so that we
    // can find all factorial of r, n
    // and n-r
 
    return (fac[n] * modInverse(fac[r], p) % p
            * modInverse(fac[n - r], p) % p)
           % p;
}



int main()
{
  c_p_c();
      
      t(x)
      {
        
        lint n;
        cin>>n;
        lint arr[n];
        fori(i,n)
        {
            cin>>arr[i];
        }

        set<lint> s;
        s.insert(arr[0]);
        bool f=true;

        for(int i=1;i<n;i++)
        {
            int a=arr[i-1];

            if(a>arr[i])
            {
                auto itr=s.lower_bound(a);

                if(itr!=s.begin() && *(--itr)>arr[i])
                {
                    f=false;
                    break;
                }
            }
            else if(a<arr[i])
            {
                 auto itr=s.upper_bound(a);

                 if(itr!=s.end() && *itr<arr[i])
                 {
                    f=false;
                    break;
                 }
            }

            s.insert(arr[i]);
        }

        if(f)
            cout<<"YES"<<endl;
        else
            cout<<"NO"<<endl;
      
      }

  return 0;
    
}
```