정렬 게임

수열을 앞에서부터 일정 길이까지만 오름차순으로 정렬하고, 다시 앞에서부터 일정 길이까지만 내림차순으로 정렬하는 과정을 반복하는 게임이다. 오름차순 정렬 한 번과 내림차순 정렬 한 번을 묶어 한 세트라고 한다.

예를 들어 수열이 [4, 1, 2, 3]이고, 첫 번째 원소부터 세 번째 원소까지 오름차순으로 정렬한 뒤 첫 번째 원소부터 두 번째 원소까지 내림차순으로 정렬하는 세트를 생각해 보자. 오름차순 정렬을 하면 [1, 2, 4, 3]이 되고, 이어서 내림차순 정렬을 하면 [2, 1, 4, 3]이 된다. 이 세트를 끝낸 결과가 [2, 1, 4, 3]이다.

수열과 $K$개의 세트가 주어진다. 세트를 주어진 순서대로 모두 진행한 뒤의 수열을 출력하는 프로그램을 작성하시오.

첫째 줄에 수열의 길이 $N$이 주어진다. ($1 \le N \le 100{,}000$)

둘째 줄에 수열의 원소 $N$개가 공백으로 구분되어 주어진다. 각 원소는 $-10{,}000$ 이상 $10{,}000$ 이하의 정수이다.

셋째 줄에 세트의 개수 $K$가 주어진다. ($1 \le K \le 100{,}000$)

넷째 줄부터 $K$개의 줄에 세트를 나타내는 두 정수 $A$, $B$가 공백으로 구분되어 주어진다. ($1 \le A \le N$, $1 \le B \le N$) 이는 첫 번째 원소부터 $A$번째 원소까지 오름차순으로 정렬한 뒤, 첫 번째 원소부터 $B$번째 원소까지 내림차순으로 정렬한다는 뜻이다. 세트는 입력에 주어진 순서대로 진행한다.

$K$개의 세트를 모두 진행한 뒤 수열의 원소 $N$개를 공백으로 구분해 한 줄에 출력한다.