#G1067. [GESP202409 四级] 区间排序

[GESP202409 四级] 区间排序

[GESP202409 四级] 区间排序

题目描述

小杨有一个包含 nn 个正整数的序列 aa。

小杨计划对序列进行多次升序排序,每次升序排序小杨会选择一个区间 [l,r][l, r](l≤rl ≤ r)并对区间内所有数字,即 al,al+1,…,ara_l, a_{l+1}, \dots, a_r 进行升序排序。每次升序排序会在上一次升序排序的结果上进行。

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

输入格式

第一行包含一个正整数 nn,含义如题面所示。

第二行包含 nn 个正整数 a1,a2,…,ana_1, a_2, \dots, a_n,代表序列。

第三行包含一个正整数 qq,代表排序次数。

之后 qq 行,每行包含两个正整数 li,ril_i, r_i,代表将区间 [li,ri][l_i, r_i] 内所有数字进行升序排序。

输出格式

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

样例 #1

样例输入 #1

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

样例输出 #1

1 3 4 5 2

样例解释

第一次升序排序后,序列为 [3,4,5,1,2][3, 4, 5, 1, 2];

第二次升序排序后,序列为 [3,4,1,5,2][3, 4, 1, 5, 2];

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

数据范围

  • 对于全部数据,保证有 1≤n≤1001 ≤ n ≤ 100,1≤ai≤1001 ≤ a_i ≤ 100,1≤q≤1001 ≤ q ≤ 100,1≤li≤ri≤n1 ≤ l_i ≤ r_i ≤ n。