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>
using namespace std;
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  long long int i, ans1, q, pos, m, t, mid, z1, g, range, j, nl, nr, x, y, k, z,
      x1, x2, x3, ans, n, one, two, curr, m1, m2, y1, y2;
  cin >> t;
  while (t-- > 0) {
    cin >> n;
    vector<long long int> a(n);
    x = 1;
    for (i = 0; i < n; i++) {
      cin >> a[i];
      if (a[i] == 1) {
        y = i;
      }
    }
    x = 1;
    for (i = y; i < n; i++) {
      if (a[i] == x) {
        x++;
      } else {
        break;
      }
    }
    if (x < n) {
      for (i = 0; i < y; i++) {
        if (a[i] == x) {
          x++;
        } else {
          break;
        }
      }
    }
    if (x == (n + 1)) {
      cout << "YES\n";
      goto z1;
    }
    x = 1;
    for (i = y; i >= 0; i--) {
      if (a[i] == x) {
        x++;
      } else {
        break;
      }
    }
    if (x < n) {
      for (i = n - 1; i > y; i--) {
        if (a[i] == x) {
          x++;
        } else {
          break;
        }
      }
    }
    if (x != (n + 1)) {
      cout << "NO\n";
      goto z1;
    }
    cout << "YES\n";
  z1:;
  }
}
