The software company SoDr is a major vendor of large software systems. One very important part of each such system is the User's Manual. SoDr recently purchased a User's Manual Generating Device (UMGD) to generate all the needed manuals automatically. The UMGD consists of several parts. The first part is a trained monkey who writes some text. The text is then processed by a formatting program and printed on a printer. The output of the printer is a long paper strip consisting of several connected pages (the paper is sometimes called "tractor paper"). Next, the paper is folded at each page boundary in such a way that the topmost page of the folded manual is the page number 1, the second page is the page number 2, etc. And in the final step the folded paper is fed into a book-making device, which cuts all the folds and binds all the papers into a brochure.
The current project of SoDr is already two weeks late. The only thing missing right now is the User's Manual. Unfortunately, one part of the UMGD is not working properly -- the printer printed the pages in wrong order. Repairing the printer would take at least several weeks. But... maybe they could still use the bad printouts, if they could fold them properly...
Given is a number N and a sequence of N distinct integers from 1 to N -- the page numbers printed on the paper in the order from left to right. You have to decide whether it is possible to fold the paper so that the page number 1 is at the top, the page number 2 is under the page number 1, etc., and the page number N is at the bottom. The folds have to be made only at page boundaries. The page orientation (e.g. which side of the page contains the text and which one is blank) in the resulting folded strip is not important.
The first line contains an integer K, the number of data sets. K data sets follow. Each data set contains the number N followed by a sequence of N distinct integers from the interval 1..N. All numbers in the input file are separated by whitespaces.
Output file contains K words separated by whitespaces. The i-th word is "YES" if it is possible to fold the paper described in the i-th data set as described above. Otherwise the i-th word should be "NO".
2 5 3 1 5 4 2 4 1 3 2 4Output file
YES NO