题目描述

全国大学生程序设计竞赛社团联合会终于发射了宇宙探测器“UCPC 1 号”！这艘探测器在显示屏上展示着算法竞赛的经典主题——数列与查询——并在宇宙中航行。

显示屏被分成 $N$ 个位置，每个位置显示一个整数。

每天午夜，显示屏上的数列会更新为另一个数列。对于每个位置 $i$，新数列的第 $i$ 个数等于前一天位置

$$l_i,l_i+1,\ldots,r_i$$

上显示的所有数中的最大值。

遗憾的是，UCPC 1 号未能顺利完成探索任务，它已经越过黑洞的事件视界，正被吸向奇点。

到达奇点时，可以认为已经经过了无限长的时间。此时，每个位置会显示：在该位置上曾经出现无穷多次的所有数中，最大的那个数。

求 UCPC 1 号到达奇点时显示屏上的数列。

输入格式

第一行包含一个整数 $N$，表示显示屏位置数量。

$$1\le N\le 300000$$

第二行包含 $N$ 个整数 $a_1,a_2,\ldots,a_N$，表示初始时各位置显示的数。

$$1\le a_i\le N$$

接下来 $N$ 行，第 $i$ 行包含两个整数 $l_i,r_i$。

$$1\le l_i\le r_i\le N$$

输出格式

输出 $N$ 个整数，依次表示 UCPC 1 号到达奇点时各位置显示的数。

样例

输入

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

输出

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],\ldots$$

因此最终答案为 $[4,3,3,4]$。