Problem M
Folding the Paper

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.

Figure 1: Folding a seven-page strip with pages in the correct order.

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.

Input

The first line of input contains the number $N \leq 10^6$. The next line contains a sequence of $N$ distinct integers from the interval $[1, N]$.

Output

Output a single line containing the word “YES” if it is possible to fold the paper as described above, and the word “NO” otherwise.

Figure 2: An example of folding a strip with wrong page order.

5
3 1 5 4 2

YES

4
1 3 2 4

NO