- Prepare
- Algorithms
- Constructive Algorithms
- Inverse RMQ

# Inverse RMQ

# Inverse RMQ

Range Minimum Query is a well-known problem: given an array of distinct integers with size and queries, find the minimum element on subsegment .

One of the most efficient and famous solutions to this problem is a *segment tree*. A segment tree is a full binary tree with nodes where the leaves contain the values of the original array and each non-leaf node contains the minimum value of its entire subtree.

Usually, a segment tree is represented as an array of integers with elements. The left child of the node is in the cell, and the right child is in the cell. For example, represents the following segment tree where the first number in a node describes the array index, , in and the second number denotes the value stored at index (which corresponds to the minimum value in that node's subtree):

You've just used *distinct* integers to construct your first segment tree and saved it as an array, , of values. Unfortunately, some evil guy came and either shuffled or altered the elements in your array. Can you use the altered data to restore the original array? If no, print `NO`

on a new line; otherwise, print two lines where the first line contains the word `YES`

and the second line contains space-separated integers denoting the array's original values. If there are several possible original arrays, print the lexicographically smallest one.

**Input Format**

The first line contains a single integer, , denoting the size of the array.

The second line contains space-separated integers denoting the shuffled values of the segment tree.

**Constraints**

- is a power of two.
- Each value in the segment tree is between and .

**Output Format**

Print `NO`

if this array could not be constructed by shuffling some segment tree. Otherwise, print `YES`

on the first line, and space-separated integers describing the respective values of the original array on the second line. If there are several possible answers, print the lexicographically smallest one.

**Sample Input 0**

```
4
3 1 3 1 2 4 1
```

**Sample Output 0**

```
YES
1 1 3 1 2 3 4
```

**Explanation 0**

This is the same segment tree shown in the *Problem Statement* above.

**Sample Input 1**

```
2
1 1 1
```

**Sample Output 1**

```
NO
```

**Explanation 1**

A segment tree with three nodes would consist of a root, a left child, and a right child. Because all three numbers in this array are the same and the leaves of the segment tree must be distinct integers, it's not possible to reconstruct the original array.