题目描述

包含$n$ 个正整数的序列$a_i$ 。
小杨计划对序列进行多次升序排序，每次升序排序小杨会选择一个区间[$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

来源

https://bas.ssoier.cn/problem_show.php?pid=4080