There are ~n~ towers in a line with distinct heights. A given tower is unstable if the tower to the immediate left and right are both shorter than it. Any unstable tower may be demolished, after which all towers are shifted together to fill the gap.

Given the initial arrangement of towers, is it possible to repeatedly demolish unstable towers to end up with just two towers left-over?

Input

The first line contains a single integer ~n~ (~2 \leq n \leq 10^5~), the number of towers initially lined up.

The next line contains ~n~ space-separated integers ~h_1,\dots,h_n~ (~1 \leq h_i \leq 10^9~). Each of the ~h_i~ are unique, and they represent the heights of each of the towers.

Output

If it is possible to reduce the line of towers to two by repeatedly demolishing unstable towers, output YES, otherwise output NO.

Example

Input 1

6
3 10 12 5 20 1

Output 1

YES

• We can demolish the tower with height 20, leaving us with 3 10 12 5 1.
• We can demolish the tower with height 12, leaving us with 3 10 5 1.
• We can demolish the tower with height 10, leaving us with 3 5 1.
• We can demolish the tower with height 5, leaving us with 3 1.

Input 2

5
3 2 5 1 10

Output 2

NO

Initially, we can only remove the tower with height 5, leaving us with 3 2 1 10. At this point, we can no longer demolish any towers.