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

[GESP202409 四级] 区间排序

Description

小杨有一个包含 nn 个正整数的序列 aa 。 小杨计划对序列进行多次升序排序,每次升序排序小杨会选择一个区间 [l,r][l,r] (lr)(l \leq r) 并对区间内所有数字,即 a1,al+1,...,ara_1,a_{l+1},...,a_r 进行升序排序。每次升序排序会在上一次升序排序的结果上进行。

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

Input Format

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

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

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

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

Output Format

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

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

1 3 4 5 2

Hint

样例解释

  • 第一次升序排序后,序列为 [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 \leq n \leq 100,1 \leq a_i \leq 100,1 \leq q \leq 100,1 \leq l_i \leq r_i \leq n$。

Source

GESP四级202409