The Korea Collegiate Programming Club Union has finally launched the space probe UCPC 1! This probe is traveling through space with a sequence and queries, the symbols of algorithm problem solving, displayed on its electronic signboard.

The signboard is divided into $N$ cells, and each cell displays an integer. This sequence changes into a different sequence every midnight; the $i$-th cell displays the maximum value among the numbers that were displayed in the $l_i, l_i+1, \dots, r_i$-th cells on the previous day.

Unfortunately, UCPC 1 failed to complete its mission and is being sucked into a singularity after passing the event horizon of a black hole. At the moment it reaches the singularity, each cell on the signboard will display the largest number among those that appear infinitely many times in that cell as time approaches infinity.

Let's find the state of the UCPC 1 signboard when it reaches the singularity.

Input

The first line contains the number of cells $N$. ($1 \le N \le 300\,000$)

The second line contains the numbers initially displayed in each cell, $a_1, \dots, a_N$, separated by spaces. ($1 \le a_i \le N$; all $a_i$ are integers)

From the third line, $N$ lines follow, each containing $l_i$ and $r_i$ separated by a space. ($1 \le l_i \le r_i \le N$)

Output

Output the numbers displayed in each cell of the signboard when UCPC 1 reaches the singularity, in order.

Examples

Input 1

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

Output 1

4 3 3 4

Note

The displayed sequence changes in order: $[1, 2, 3, 4], [4, 3, 3, 2], [3, 3, 3, 4], [4, 3, 3, 3], [3, 3, 3, 4], [4, 3, 3, 3], \dots$.