Book Shelf Arrangement

Tin hates when books are not arranged in order. Ante decides to help him by reordering the books using the following operations. There is a pile of books, two hands (left and right) and a left shelf. Initially, the pile contains n books given in order (the first number is the top‐most book). Both hands are empty and the shelf is empty.

In each step, you can perform one of the following operations:

• If at least one hand is empty, you may take the book from the top of the pile and hold it in that empty hand. (You decide whether to use the left or right hand.)
• If a hand is holding a book, you may place that book onto the top of the shelf.

The final goal is to achieve an arrangement on the left shelf such that the books, when read from the top to the bottom, are in increasing order of thickness (i.e. from thin to thick). Since every time you place a book it is put on top of the shelf, the push order must be strictly decreasing (i.e. if the push order is P₁, P₂, ..., P_k then we require $$P_k < P_{k-1} < \cdots < P_1.$$

Given the number of books, and their thicknesses from the pile (from top to bottom), determine if there exists a sequence of allowed operations that results in the left shelf being arranged as required. Output YES if it is possible; otherwise output NO.

inputFormat

The first line contains an integer n (1 ≤ n ≤ 50), representing the number of books.

The second line contains n positive integers, representing the thicknesses of the books in the pile from top to bottom.

outputFormat

Output a single line: YES if it is possible to arrange the books on the shelf in the required order, or NO if it is not possible.

sample

3
3 2 1

YES