全国大学生编程社团联合会终于发射了宇宙探测器 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$。