There are n students standing in a circle in some order. The index of the i-th student is p_i. It is guaranteed that all indices of students are distinct integers from 1 to n (i. e. they form a permutation).

Students want to start a round dance. A clockwise round dance can be started if the student 2 comes right after the student 1 in clockwise order (there are no students between them), the student 3 comes right after the student 2 in clockwise order, and so on, and the student n comes right after the student n - 1 in clockwise order. A counterclockwise round dance is almost the same thing — the only difference is that the student i should be right after the student i - 1 in counterclockwise order (this condition should be met for every i from 2 to n). 

For example, if the indices of students listed in clockwise order are [2, 3, 4, 5, 1], then they can start a clockwise round dance. If the students have indices [3, 2, 1, 4] in clockwise order, then they can start a counterclockwise round dance.

Your task is to determine whether it is possible to start a round dance. Note that the students cannot change their positions before starting the dance; they cannot swap or leave the circle, and no other student can enter the circle. 

You have to answer q independent queries.

Input

The first line of the input contains one integer q (1 ≤ q ≤ 200) — the number of queries. Then q queries follow.

The first line of the query contains one integer n (1 ≤ n ≤ 200) — the number of students.

The second line of the query contains a permutation of indices p_1, p_2, ..., p_n (1 ≤ p_i ≤ n), where p_i is the index of the i-th student (in clockwise order). It is guaranteed that all p_i are distinct integers from 1 to n (i. e. they form a permutation).

Output

For each query, print the answer on it. If a round dance can be started with the given order of students, print "YES". Otherwise print "NO".

Example

Input


5
4
1 2 3 4
3
1 3 2
5
1 2 3 5 4
1
1
5
3 2 1 5 4


Output


YES
YES
NO
YES
YES
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace std;
using namespace __gnu_pbds; 
#define ll                      long long int
#define pb                      push_back
#define rep(i,a,b,c)            for(ll i=(a);i<=(b);i+=(c))
#define repb(i,a,b,c)           for(ll i=(a);i>=(b);i-=(c))
#define MOD                     1000000007
#define ld                      long double
#define mp                      make_pair
#define vpll                    vector<pair<ll,ll>>
#define vll                     vector<ll>
#define vld                     vector<ld>
#define vvll                    vector<vector<ll>>
#define vvld                    vector<vector<ld>>
#define pll                     pair<ll,ll>
#define pqll                    priority_queue<ll>
#define mll                     map<ll,ll>
#define mlc                     map<ll,char>
#define um                      unordered_map
#define umll                    um<ll,ll>
#define umlc                    um<ll,char>
#define all(x)                  x.begin(),x.end()
#define ff                      first
#define ss                      second
#define ln                      cout<<"\n";
#define endl                    "\n"
#define test                    ll T;cin>>T;while(T--)
#define isvowel(a)              (a == 'a' || a == 'e' || a == 'i' || a == 'o' || a == 'u')
#define fastIO                  ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define show(w,size)            for(ll i=0;i<size;i++) cout<<w[i]<<" "; 
#define print(a)                cout<<a<<"\n";
#define mset(dp,no)             memset(dp,no,sizeof(dp))
#define input(a,n)              rep(i,0,n-1,1) cin>>a[i];
#define countbit                __builtin_popcount                                           //Number of setbits in decimal notation
#define fbo(k)                  find_by_order(k)    //Valid for ordered set                  //Number of items strictly smaller than k
#define ook(k)                  order_of_key(k)     //Valid for ordered set                  //K-th element in a set (counting from zero) 
#define lb(v,val)               lower_bound(all(v),val)-v.begin()
#define ub(v,val)               upper_bound(all(v),val)-v.begin()  
#define in                      insert   
#define SS                      stringstream
//#define db(x) cout <<#x<<": "<<x<<'\n';
#define ordered_set             tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> 
#define db(...)                 __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1) { cerr << name << " : " << arg1 <<'\n'; }
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args) {
    const char* comma = strchr(names + 1, ',');
    cerr.write(names, comma - names) << " : " << arg1 << " | "; __f(comma + 1, args...);
}  
 
ll gcd(ll a,ll b){if(a<b)return gcd(b,a);else if(b==0)return a;else return gcd(b,a%b);}
ll isPrime(ll n){ll p=(ll)sqrt(n);rep(i,2,p,1) if(n%i==0) return 0;return 1;}// reuturn 1 if prime
ll pow(ll b,ll e){if(e==0)return 1;else if(e%2==0){ll a=pow(b,e/2);return a*a;}else {ll a=pow(b,e/2);return b*a*a;}}
ll powm(ll x,ll y,ll m=MOD){x=x%m;ll res=1;while(y){if(y&1)res=res*x;res%=m;y=y>>1;x=x*x;x%=m;}return res;}
ll lcm(ll a,ll b){ return (a*b)/gcd(a,b);}
ll modInverse(ll a, ll m) { return powm(a, m-2, m);}
bool issq(ll n){ ll p=sqrt(n);return p*p==n;}
 
 
vll prime;
void seive(ll n)
{
    prime.resize(n+1,1);
    prime[0] = 0, prime[1] = 0;
    for (ll i = 2; i*i <= n; i++)
        if (prime[i])
            for (ll j = i * i; j <= n; j += i)
                prime[j] = 0;
}
 
 
ll extended_GCD(ll a ,ll b ,ll &x ,ll &y){
    if(a == 0){
        x = 0;
        y = 1;
        return b;
    }
    ll x1 , y1;
    ll gcd = extended_GCD(b%a , a , x1 , y1);
    x = y1 - (b/a)*x1;
    y = x1;
    return gcd;
}
    ll mulInv(ll a , ll mod=MOD)
	{
    ll x , y;
    extended_GCD(a , mod , x , y);
    if(x < 0) x += mod;
    return x;
}
 
 
ll find(ll num[], ll rem[], ll k,ll prod)
{
    // Compute product of all numbers
    ll result = 0;
    // Apply above formula
    for (ll i = 0; i < k; i++)
    {
        ll pp = prod / num[i];
        result += rem[i] * mulInv(pp, num[i]) * pp;
    }
 
    return result % prod;
}

bool cmp(pair<ll,ll>&p1,pair<ll,ll>&p2)
{
  if(p1.ff==p2.ff)
  {
    return p1.ss>p2.ss;
  }
  return p1.ff<p2.ff;
}
bool isPalindrome(string s)
{
  ll i,j;
  for(i=0,j=s.length()-1;i<=j;i++,j--)
  {
    if(s[i]!=s[j])
    {
      return 0;
    }
  }
return 1;
}
 
bool isSubSeq(string str1, string str2, ll m, ll n)
{
    // Base Cases
    if (m == 0) return true;
    if (n == 0) return false;
    // If last characters of two strings are matching
    if (str1[m-1] == str2[n-1])
        return isSubSeq(str1, str2, m-1, n-1);
    // If last characters are not matching
    return isSubSeq(str1, str2, m, n-1);
}
 
void modBigNumber(string num, ll m) 
{ 
    // Store the modulus of big number 
    vector<int> vec; 
    ll mod = 0; 
  
    // Do step by step division 
    for (int i = 0; i < num.size(); i++) { 
           
        int digit = num[i] - '0'; 
  
        // Update modulo by concatenating 
        // current digit. 
        mod = mod * 10 + digit; 
  
        // Update quotient  
        int quo = mod / m; 
        if((vec.size()!=0)||(quo!=0))        //to remove initiale zeros
        vec.push_back(quo); 
        // Update mod for next iteration. 
        mod = mod % m;         
    } 
   // cout << "\nRemainder : " << mod << "\n"; 
   // cout << "Quotient : ";rep(i,0,vec.size()-1,1)cout<<vec[i];cout<<"\n"; 
    return; 
} 
 
ll sumofdigits(ll a)
{
	ll val=0;
	while(a>0)
	{
		val+=a%10;
		a/=10;
	}
	return val;
}

ll stn(string s)       //stn=string_to_number
{
	SS s1;
	s1<<s;
	ll num;
	s1>>num;
	return num;
}

string nts(ll n)       //nts=number_to_string 
{
	SS s1;
	s1<<n;
	string s;
	s1>>s;
	return s;
}

//Binary Index Tree or Fenwick Tree
ll sumBIT(ll bitree[],ll n)                 //n=index till sum is to be calculated
{
	
	ll sum=0;
	n++;
	while(n>0)
	{
		sum+=bitree[n];
		n-=(n&-n);
	}
	return sum;
}

void updateBIT(ll bitree[],ll n,ll val,ll index)
{
index++;	
while(index<=n)
{
	bitree[index]+=val;
	index+=(index&-index);
}
}


class DSU
{
	public:
		vll v,rank;
	
		DSU(ll n)
		{
		    v.resize(n+1);
			rank.resize(n+1);
			rep(i,1,n,1)
			v[i]=i;
		}
		
		ll find_set(ll a)
		{
			if(v[a]==a)
				return a;
			else
				return v[a]=find_set(v[a]);
		}
		
		void union_sets(ll a,ll b)
		{
			a=find_set(a);
			b=find_set(b);
			if(a!=b)
			{
				if(rank[a]<rank[b])
					v[a]=b;
				else 
				{
					v[b]=a;
					if(rank[a]==rank[b])
						rank[a]++;
				}	
			}
		}
};
  
using namespace std;
int main()
{
	fastIO
	test{
	ll n,index;
	string ans="YES";
	cin>>n;
	ll a[n];
	input(a,n);
	rep(i,0,n-1,1)
	if(a[i]==1)
	{
		index=i;
		break;
	}
//	db(index);
	if(index<n-1)
	{
		//db(a[index+1]);
		if(a[index+1]==2)
		{
		rep(i,index+1,n-1,1)
		if(a[i]!=(a[i-1]+1))
		{ans="NO";
	//	cout<<"hdrd";
		goto x;
		}
		}
		else if(a[index+1]==n)
		{
		rep(i,index+2,n-1,1)
		{
			if(a[i]!=(a[i-1]-1))
			ans="NO";
	//		cout<<"ddnbd";
			goto x;
		}
	}
		else 
		{
	//	cout<<"dndd";
		ans="NO";
	goto x;
	}}
	if(index>0)
	{
		if(a[index-1]==2)
		{
		repb(i,index-1,0,1)
		if(a[i]!=a[i+1]+1)
		{ans="NO";
		goto x;
		}
		}
		else if(a[index-1]==n)
		{
		repb(i,index-2,0,1)
		if(a[i]!=a[i+1]-1)
		{ans="NO";
		goto x;
		}
		}
		else 
		{ans="NO";
		goto x;
		}
	}
	x:
	cout<<ans<<"\n";
	}
	return 0;
}
