重新排序

本题总分：20 分

【问题描述】

给定一个数组 A 和一些查询 Li, Ri，求数组中第 Li 至第 Ri 个元素之和。

小蓝觉得这个问题很无聊，于是他想重新排列一下数组，使得最终每个查

询结果的和尽可能地大。小蓝想知道相比原数组，所有查询结果的总和最多可

以增加多少?

【输入格式】

输入第一行包含一个整数 n。

第二行包含 n 个整数 A1, A2, · · · , An，相邻两个整数之间用一个空格分隔。

第三行包含一个整数 m 表示查询的数目。

接下来 m 行，每行包含两个整数 Li、Ri ，相邻两个整数之间用一个空格分

隔。

【输出格式】

输出一行包含一个整数表示答案。

【样例输入】

5

1 2 3 4 5

2

1 3

2 5

【样例输出】

4