25392번 - 사건의 지평선

전국 대학생 프로그래밍 동아리 연합이 드디어 우주 탐사선 UCPC 1호를 발사했다! 이 탐사선은 알고리즘 문제 풀이의 상징인 수열과 쿼리를 전광판에 표시한 채 우주를 여행하고 있다.

전광판은 $N$개의 칸으로 나누어져 있고, 각 칸에는 하나의 정수가 표시되어 있다. 이 수열은 매일 자정에 다른 수열로 바뀌는데, $i$번째 칸에는 전날 $l_i,l_i+1,\cdots ,r_i$번째 칸에 표시되어 있던 수 중 가장 큰 값이 표시된다.

아쉽게도, UCPC 1호는 탐사를 성공적으로 마치지 못하고 블랙홀의 사건의 지평선을 지나 특이점으로 빨려 들어가고 있다. 특이점에 도달하는 순간, 전광판의 각 칸에는 무한한 시간이 흐를 때 그 칸에 무한 번 표시되는 수들 중 가장 큰 수가 표시된다.

특이점에 도달한 UCPC 1호의 전광판의 모습을 구해보자.

첫 번째 줄에는 칸의 개수 $N$이 주어진다. $(1\leq N\leq 300\, 000)$

두 번째 줄에는 각 칸에 최초로 표시된 수 $a_1,\cdots ,a_N$이 공백으로 구분되어 차례로 주어진다. $(1\leq a_i\leq N;$ 모든 $a_i$는 정수$)$

세 번째 줄부터 $N$개의 줄에 걸쳐 $l_i,r_i$가 공백으로 구분되어 차례로 주어진다. $(1\leq l_i\leq r_i\leq N)$

UCPC 1호가 특이점에 도달했을 때, 전광판의 각 칸에 표시되는 수를 차례로 출력한다.