U332137 区间求和与排序

给定一个包含 $n$ 个正整数的数组 $a$，你需要回答 $t$ 个询问。每个询问给出两个整数 $l$ 和 $r$，要求计算数组 $a$ 在区间 $[l, r]$ 内的元素之和，并让数组 $[l, r]$ 部分从大到小排序，最后输出数组 $a$。

第一行一个整数 $n$ 。 第二行 n 个整数 $a_i$，用空格分隔。 第三行一个整数 $t$ 。 接下来 $t$ 行，每行两个整数 $l_i$, $r_i$，用空格分隔。

每次查询返回区间 $[l, r]$ 的和，并将数组 $[l, r]$ 部分从大到小排序（排序不影响区间和，你可以想成两个数组，一个排序，一个求和），查询结束后最后返回数组 $a$ （排序过的），用空格分隔。

### 【样例解释】 【样例 #1 解释】 第一行：为第一次询问，区间 $[1, 3]$ 的和为6，并将数组 $[1, 3]$ 区间进行降序排序。 第二行：为第二次询问，区间 $[3, 5]$ 的和为12，并将数组 $[3, 5]$ 区间进行降序排序。 第三行：查询结束，返回现在的数组。 ### 【数据范围】 对于 $100\%$ 的数据， $1 \leq n \leq 10^{5}$ ， $1 \leq t \leq 10^{3}$ ， $1 \leq l_i < r_i \leq n$，$1 \leq a_i \leq 10^{3}$。