# Heap

A heap is a specialized tree data structure that satisfies the heap property:

πΌ

If

`P`

is a parent node of `C`

, then the value of `P`

is greater than or equal to (in a max-heap) or less than or equal to (in a min-heap) the value of C.There are two main types of heaps:

- Max Heap: The value of the parent node should be
**larger**than or equal to its child nodes.

- Min Heap: The value of the parent node should be
**smaller**than or equal to its child nodes.

Weβll concentrate on the max-heap as most of the standard libraries implement a max-heap for priority queues. In a max-heap, the root of the tree is the largest element, while the leaves are the smallest. Yet, there is no particular order for the leaf nodes. So, the only guarantee is that the root node is the largest one and its child nodes are smaller than or equal to its value.

Note that the last row of the heap is always filled from left to right. So, the leftmost leaf is filled the first and the rightmost leaf is filled the last - as demonstrated in the picture above.

Implementation

A heap can be implemented as an array, with the first element of the array representing the root node. As each node has only 2 child nodes, we can arrange the indexing as:

- The root element has an index of 1.

- The left and right children are located at
`2i`

and`2i+1`

respectively for all the nodes.

- The parent node of an element at index
`i`

is located at index`i // 2`

.

The heap above can be written in a list as:

```
# Just read every line in the picture and write the numbers side by side
heap = [None, 8, 5, 7, 1, 1, 6, 3, 1]
# Or to see it better visually
heap = [None, # We skip the index [0] to have a simpler indexing
8, # Index [1]
5, 7, # Indices [2, 3]
1, 1, 6, 3, # Indices [4, 5, 6, 7]
1] # Index [8]
```

Β

Challenge: Check if the binary tree is a heap

Given a binary tree represented with an array of

`n`

numbers (with indexing described above), you are asked to check if it satisfies the max-heap properties. Input

The first line of the input contains a single integer

`n`

(1 β€ n β€ 100 000).The next line contains

`n`

space-separated integers () representing the values of the elements in the heap. Output

The program should print

`Yes`

in case the input binary tree satisfies the max-heap property, and `No`

otherwise. Examples

Input | Output |

8
8 5 7 1 1 6 3 1 | Yes |

7
8 5 7 1 9 6 3 | No |

Explanation

Example 1

Β

Example 2

#### Constraints

Time limit: 2 seconds

Memory limit: 512 MB

Output limit: 1 MB