背景

GESP四级真题(202409)

描述

⼩杨有⼀个包含 $n$ 个正整数的序列 。

⼩杨计划对序列进⾏多次升序排序，每次升序排序⼩杨会选择⼀个区间 $[l, r] (l \le r)$ 并对区间内所有数字，即$a_l, a_{l+1}, ... , a_r$进⾏升序排序。每次升序排序会在上⼀次升序排序的结果上进⾏。

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

格式

输入

第⼀⾏包含⼀个正整数 $n$ ，含义如题⾯所⽰。 第⼆⾏包含 个正整数 $n$，代表序列$a_1, a_2, ..., a_n$。 第三⾏包含⼀个正整数 $q$ ，代表排序次数。 之后 $q$ ⾏，每⾏包含两个正整数 $l_i, r_i$ ，代表将区间 $[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,1,2]$ ；

第⼆次升序排序后，序列为 $[3,4,1,5,2]$ ；

第三次升序排序后，序列为 $[1,3,4,5,2]$；

数据规模

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

限制

时间限制：1.0 s

空间限制：512.0 MB