e-olymp
favorite We need a little bit of your help to keep things running, click on this banner to learn more

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 (1in) next conditions must hold:

  • If 2in, then aia2i;
  • If 2i + 1n, then aia2i+1;

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

Input

First line contains number n (1n105). Second line contains n integers that do not exceed 2 * 109 by absolute value.

Output

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

prb3737.gif

Time limit 1 second
Memory limit 128 MiB
Input example #1
7
3 10 5 12 11 6 7
Output example #1
YES