全国大学プログラミングサークル連合がついに宇宙探査機「UCPC 1号」を打ち上げた！この探査機は、アルゴリズム問題の象徴である数列とクエリを電光掲示板に表示したまま宇宙を旅している。

電光掲示板は $N$ 個のマスに分かれており、各マスには一つの整数が表示されている。この数列は毎日深夜0時に別の数列に変わる。$i$ 番目のマスには、前日に $l_i, l_i + 1, \dots, r_i$ 番目のマスに表示されていた数のうち、最大の値が表示される。

残念ながら、UCPC 1号は探査を成功裏に終えることができず、ブラックホールの事象の地平線を越えて特異点へと吸い込まれている。特異点に到達した瞬間、電光掲示板の各マスには、無限の時間が流れたときにそのマスに無限回表示される数のうち、最も大きい数が表示される。

特異点に到達したUCPC 1号の電光掲示板の様子を求めよ。

入力

最初の行にはマスの個数 $N$ が与えられる。($1 \le N \le 300\,000$)

二番目の行には、各マスに最初に表示された数 $a_1, \dots, a_N$ が空白区切りで順に与えられる。($1 \le a_i \le N$; すべての $a_i$ は整数)

三番目の行から $N$ 行にわたって、$l_i, r_i$ が空白区切りで順に与えられる。($1 \le l_i \le r_i \le N$)

出力

UCPC 1号が特異点に到達したとき、電光掲示板の各マスに表示される数を順に出力せよ。

入出力例

入力 1

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

出力 1

4 3 3 4

注記

表示される数列は順に $[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$ である。