重新排序 ### 问题描述 给定一个数组 $A$ 和一些查询 $L_{i}, R_{i}$, 求数组中第 $L_{i}$ 至第 $R_{i}$ 个元素之和。 小蓝觉得这个问题很无聊, 于是他想重新排列一下数组, 使得最终每个查 询结果的和尽可能地大。小蓝想知道相比原数组, 所有查询结果的总和最多可 以增加多少? ### 输入格式 输入第一行包含一个整数 $n$ 。 第二行包含 $n$ 个整数 $A_{1}, A_{2}, \cdots, A_{n}$, 相邻两个整数之间用一个空格分隔。 第三行包含一个整数 $m$ 表示查询的数目。 接下来 $m$ 行, 每行包含两个整数 $L_{i} 、 R_{i}$, 相邻两个整数之间用一个空格分 隔。 ### 输出格式 输出一行包含一个整数表示答案。 ### 样例输入 ```txt 5 1 2 3 4 5 2 1 3 2 5 ``` ### 样例输出 ```text 4 ``` ### 样例说明 原来的和为 $6+14=20$, 重新排列为 $(1,4,5,2,3)$ 后和为 $10+14=24$, 增 加了 4。 ### 评测用例规模与约定 对于 $30 \\%$ 的评测用例， $n, m \leq 50$; 对于 $50 \\%$ 的评测用例, $n, m \leq 500$; 对于 $70 \\%$ 的评测用例, $n, m \leq 5000$; 对于所有评测用例, $1 \leq n, m \leq 10^{5}, 1 \leq A_{i} \leq 10^{6}, 1 \leq L_{i} \leq R_{i} \leq 10^{6}$ 。