Is it a Heap? - Problems

The Heap data structure can be implement using an array.

The array must maintain the main Heap property: for each i (1 ≤ i ≤ n) next conditions must be hold:

If 2i ≤ n, then a[i]≤a[2i]
If 2i+1 ≤ n, then a[i]≤a[2i+1]

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

Input

The first line contains the number n (1 ≤ n ≤ 10⁵). The second line contains n integers to exceeding 2·10⁹.

Output

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

Time limit 1 second

Memory limit 64 MiB

Input example #1

89656
-999985067 -999973389 -999901720 -999824388 -999927808 -999619842 -999867299 -999753770 -999734312 -999863984 -999537843 -998667069 -999434202 -999814166 -999818890 -999698485 -999734503 -998966337 -999195731 -999855904 -999589028 -999441809 -999149448 -998531036 -998155293 -998704535 -999152619 -999008122 -998351652 -999498460 -999799474 -997531888 -999663151 -999037955 -998771371 -998833439 -998243660 -998426462 -998605706 -999365187 -998762608 -999347009 -999289540 -997194072 -999033149 -999109939 -998370982 -998093117 -997207454 -997072134 -996620661 -998073780 -998618717 -998995713 -998376788 -998450094 -998667310 -998102284 -996552156 -999358563 -998311636 -997543022 -999042186 -996425481 -997014054 -999557398 -999453881 -996441345 -998205275 -995933200 -997725588 -996007972 -998333966 -997092105 -996601837 -997528911 -996477272 -997404892 -997383257 -998493907 -999362495 -997165116 -998526367 -998711189 -998059161 -998151708 -999059284 -993176548 -995062782 -998638748 -996
...

Output example #1

YES