区间排序

题目描述

小杨有一个包含 $n$ 个正整数的序列 $a$。

小杨计划对序列进行多次升序排序，每次排序会选择区间 $[l,r]$（$l \le r$）并对该区间内的所有数字 $a_l, a_{l+1}, \dots, a_r$ 进行升序排序。每次升序排序在上一次排序的结果上进行。

小杨想请你计算出多次升序排序后的序列。

输入格式

第一行包含一个正整数 $n$，含义如题面所示。
第二行包含 $n$ 个正整数 $a_1, a_2, \dots, a_n$，代表序列 $a$。
第三行包含一个正整数 $q$，代表排序次数。
之后 $q$ 行，每行包含两个正整数 $l, r$，代表将区间 $[l_i, r_i]$ 内所有数字进行升序排序。

输出格式

输出一行包含 $n$ 个正整数，代表多次升序排序后的序列。

样例输入

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

样例输出

1 3 4 5 2

样例解释

对于样例，初始序列为 $[3,4,5,2,1]$。
第一次升序排序区间 $[4,5]$，对第 $4$、$5$ 个数 $2,1$ 升序排序，序列变为 $[3,4,5,1,2]$；
第二次升序排序区间 $[3,4]$，对第 $3$、$4$ 个数 $5,1$ 升序排序，序列变为 $[3,4,1,5,2]$；
第三次升序排序区间 $[1,3]$，对第 $1$ 到 $3$ 个数 $3,4,1$ 升序排序，序列变为 $[1,3,4,5,2]$。
最终输出序列 $1\ 3\ 4\ 5\ 2$。

数据范围

对于全部的测试数据，保证 $1 \le n, a_i, q \le 100$，$1 \le l_i \le r_i \le n$。