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
import java.io.*;
import java.util.*;
import java.math.*;

public class CircleofStudents {

	public static void main(String[] args) throws Exception {
		Reader file = new Reader();
		int q = file.nextInt();

		for (int asdf = 0; asdf < q; asdf++) {
			int n = file.nextInt();
			int[] nums = new int[n];

			int oneIndex = -1;

			for (int i = 0; i < n; i++) {
				nums[i] = file.nextInt();
				if (nums[i] == 1) {
					oneIndex = i;
				}
			}

			if (n == 1) {
				System.out.println("YES");
				continue;
			}

			boolean clock = true;
			boolean anti = true;

			int i = oneIndex;
			int end = oneIndex - 1;
			if (end < 0) {
				end = n - 1;
			}
			while (i != end) {
				if (i >= n) {
					i = 0;
				}
				int plus = i + 1;
				if (plus >= n) {
					plus = 0;
				}

				if (nums[i] != nums[plus] - 1) {
					clock = false;
					break;
				}
				i++;
			}

			i = oneIndex;
			end = oneIndex + 1;
			if (end >= n) {
				end = 0;
			}
			while (i != end) {
				if (i < 0) {
					i = n - 1;
				}
				int minus = i - 1;
				if (minus < 0) {
					minus = n - 1;
				}
				if (nums[i] != nums[minus] - 1) {
					anti = false;
					break;
				}
				i--;
			}

			System.out.println((clock || anti) ? "YES" : "NO");
		}

	}

	static class Reader {
		private final int BUFFER_SIZE = 1 << 16;
		private char nullChar = (char) 0;
		private byte[] buf = new byte[BUFFER_SIZE];
		private int bufferPointer, bytesRead;
		private char c = nullChar;
		private BufferedInputStream in;
		private char delimeter = ' ';

		public void close() throws IOException {
			in.close();
		}

		public Reader() {
			in = new BufferedInputStream(System.in, BUFFER_SIZE);
			bufferPointer = bytesRead = 0;
		}

		public Reader(InputStream read) {
			in = new BufferedInputStream(read, BUFFER_SIZE);
			bufferPointer = bytesRead = 0;
		}

		public Reader(String s) throws FileNotFoundException {
			try {
				in = new BufferedInputStream(new FileInputStream(new File(s)), BUFFER_SIZE);
			} catch (FileNotFoundException e) {
				throw new FileNotFoundException();
			}
			bufferPointer = bytesRead = 0;
		}

		private char nextChar() {
			while (bufferPointer == bytesRead) {
				try {
					bytesRead = in.read(buf);
				} catch (Exception e) {
					return nullChar;
				}
				if (bytesRead == -1) {
					return nullChar;
				}
				bufferPointer = 0;
			}
			try {
				return (char) buf[bufferPointer++];
			} catch (ArrayIndexOutOfBoundsException e) {
				throw new NoSuchElementException("No Line Found");
			}
		}

		public String next() {
			StringBuilder res = new StringBuilder();
			while (c < 32 || c == delimeter)
				c = nextChar();
			while (c != nullChar) {
				if (c == '\n' || c == '\r' || c == delimeter) {
					break;
				}
				res.append(c);
				c = nextChar();
			}
			if (c == '\n')
				c = nextChar();
			return res.toString();
		}

		public String nextLine() {
			StringBuilder res = new StringBuilder();
			while (c == delimeter) {
				c = nextChar();
			}
			while (c != nullChar) {
				if (c == '\n' || c == '\r') {
					c = nextChar();
					break;
				}
				res.append(c);
				c = nextChar();
			}
			if (c == '\n')
				c = nextChar();
			return res.toString();
		}

		/**
		 * Note: Setting the delimeter to "-" will remove the methods ability to read
		 * negatives.
		 */
		public int nextInt() {
			return (int) nextLong();
		}

		/**
		 * Note: Setting the delimeter to "-" will remove the methods ability to read
		 * negatives.
		 */
		public long nextLong() {
			while (c == delimeter || c < 32)
				c = nextChar();
			if (c < '0' && c != '-' || c > '9')
				throw new InputMismatchException("" + c);
			boolean neg = (c == '-');
			if (neg)
				c = nextChar();
			long res = 0;
			do {
				res = (res << 3) + (res << 1) + c - '0';
			} while ((c = nextChar()) >= '0' && c <= '9');
			return neg ? -res : res;
		}

		/**
		 * Note: Setting the delimeter to "-" or "." may remove the methods ability to
		 * read negatives or decimals.
		 */
		public double nextDouble() {
			while (c == delimeter || c < 32)
				c = nextChar();
			if (c < '0' && c != '-' && c != '.' || c > '9')
				throw new InputMismatchException("" + c);
			boolean neg = (c == '-');
			if (neg)
				c = nextChar();
			double res = 0.0;
			while (c >= '0' && c <= '9') {
				res = res * 10 + c - '0';
				c = nextChar();
			}
			if (c == '.') {
				double div = 1;
				while ((c = nextChar()) >= '0' && c <= '9') {
					res += (c - '0') / (div *= 10);
				}
			}
			return neg ? -res : res;
		}

		public BigInteger nextBigInteger() {
			while (c == delimeter || c < 32)
				c = nextChar();
			if (!Character.isDigit(c) && c != '-') {
				throw new InputMismatchException();
			}
			StringBuilder strNum = new StringBuilder();
			if (c == '-') {
				strNum.append("-");
				c = nextChar();
			}
			while (Character.isDigit(c)) {
				strNum.append(c);
				c = nextChar();
			}
			return new BigInteger(strNum.toString());
		}

		public BigDecimal nextBigDecimal() {
			while (c == delimeter || c < 32)
				c = nextChar();
			if (!Character.isDigit((c)) && c != '-' && c != '.')
				throw new InputMismatchException();
			StringBuilder strNum = new StringBuilder();
			if (c == '-') {
				strNum.append("-");
				c = nextChar();
			}
			while (Character.isDigit(c) || c == '.') {
				strNum.append(c);
				c = nextChar();
			}
			return new BigDecimal(strNum.toString());
		}

		public char delimeter() {
			return delimeter;
		}

		public void useDelimeter(char c) {
			delimeter = c;
		}

		public boolean hasNext() throws IOException {
			if (c >= 32)
				return true;
			in.mark(BUFFER_SIZE);
			char save = c;
			int savePointer = bufferPointer;
			while (true) {
				c = nextChar();
				if (bytesRead == -1 || c == nullChar)
					return false;
				if (c >= 32) {
					return true;
				}
				if (c == '\n' || c == '\r') {
					for (int i = 0; i < 2; i++) {
						c = nextChar();
						if (c >= 5) {
							in.reset();
							c = save;
							bufferPointer = savePointer;
							return true;
						}
						if (bytesRead == -1 || c == nullChar)
							return false;
					}
				}
			}
		}
	}
}