Is it a Heap?

The Heap data structure can be implement using an array.

The array must maintain the main heap property: for each $i(1\le i\le n)$ next conditions must hold:

• If $2i\le n$, then $a_i\le a_{2i}$

• If $2i+1\le n$, then $a_i\le a_{2i+1}$

The array of integers is given. Determine whether it is a heap.

Input

First line contains number $n(1\le n\le 10^5)$. Second line contains $n$ integers that do not exceed $2\cdot 10^9$ by absolute value.

Output

Print "YES", if the array is a heap and "NO" otherwise.

Examples