0 #2858. 区间排序【GESP四级-2024.09】

区间排序【GESP四级-2024.09】

[GESP202409 四级] 区间排序

题目描述

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

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

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

输入格式

第一行包含一个正整数 nn,含义如题面所示。
第二行包含 nn 个正整数 a1,a2,ana_1, a_2, \dots a_n,代表序列 aa
第三行包含一个正整数 qq,代表排序次数。
之后 qq 行,每行包含两个正整数 l,rl, r,代表将区间 [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

提示

样例 1 解释

  • 第一次升序排序后,序列为 [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]

数据规模与约定

对于全部的测试数据,保证 1n,ai,q1001 \leq n, a_i, q \leq 1001lirin1 \leq l_i \leq r_i \leq n