There are ~n~ students about to undertake their FIT1008 hurdle test. These students have student IDs ranging from ~1~ to ~n~.

However, test check-in needs to follow a very specific procedure. Jackson mistakenly implemented the test check-in with a queue data structure, meaning that he needs to check in students in order of their student ID (for example, the student with ID 5 must be checked in before the student with ID 6 can be checked in).

However, the students, eager to undertake their test, have already lined up for the test! The entrance to the room is very cramped, so Jackson has proposed a 2-queue solution:

1. All students start in the first queue, in the order specified in the input.
2. Jackson is allowed to take the student from the front of the first queue and place them at the front of the second queue.
3. No one can be placed back into the first queue (there are too many angry students to ask them to move back).
4. Jackson can only check in students from the front of the first queue or the front of the second queue.

Can you determine whether it is possible for Jackson to check in all students?

In order to pass the tests, your solution should have a time complexity of ~O(n)~.

Input

Input will begin with a single integer ~n~ (~1 \leq n \leq 3 \times 10^5~), the number of students.

The next line will contain some ordering of the integers ~1~ to ~n~, ~a_1, a_2, \ldots, a_n~ (~1 \leq a_i \leq n~) - the student IDs in queue order. The first value is the front of the queue, and the last is the back of the queue.

Output

Simply output YES or NO, based on whether it is possible for Jackson to check in everyone for the test.

Example 1

Input

5
1 2 5 4 3

Output

YES

It is possible for Jackson to check in everyone. He can check in students 1 and 2, then move student 5 to the second queue, and then student 4 to the second queue (now in front of 5).

Then he checks in student 3 from the first queue, and students 4 and 5 from the second queue.

Example 2

Input

5
3 5 2 1 4

Output

NO

It is not possible for Jackson to check in these students.