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 a positive integer K < 200, the number of data sets. K data sets follow. Each
data set contains a positive number N < 3,000 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".
Input file
2
5 3 1 5 4 2
4 1 3 2 4
Output file
YES
NO
e-mails
questions: ipscreg(at)ksp(dot)sk
webmaster: webmaster(at)ksp(dot)sk