Paper Folding
InterviewTime limit2sMemory limit128 MB
Decide whether a strip of N labeled cells can be folded so the stack reads 1 to N from top to bottom, checking labels against the shrinking strip's two ends.
- Level
Medium5 of 10
- Topics
- Two pointers, Simulation, Array
- Solved
- No attempts yet
Problem
A sheet of paper consists of N square cells connected in one row. Each cell contains exactly one integer from 1 through N.
You may fold the paper several times along the boundary between two neighboring cells. Determine whether it is possible to fold the whole sheet into one stack whose labels are ordered from top to bottom as 1, 2, 3, ..., N.
Input
The first line contains the number of data sets T.
Each data set consists of two lines. The first line contains the length N of the paper. The second line contains the integers 1 through N, separated by spaces, in their current order on the paper.
T is a positive integer not greater than 10, and N is a positive integer not greater than 2,000.
Output
For each data set, print YES on one line if the paper can be folded into a stack ordered from top to bottom as 1, 2, 3, ..., N. Otherwise, print NO.