全國大學生程式設計社團聯合會終於發射了宇宙探測船 UCPC 1 號！這艘探測船帶著象徵演算法問題解法的數列與查詢，在宇宙中旅行，並將其顯示在電子看板上。

電子看板被劃分為 $N$ 個格子，每個格子顯示一個整數。這個數列每天午夜都會變更為另一個數列，第 $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$。