问题描述

给定一个数组 $A$ 和一些查询 $L_{i}, R_{i}$ , 求数组中第 $L_{i}$ 至第 $R_{i}$ 个元素之和。

小蓝觉得这个问题很无聊, 于是他想重新排列一下数组, 使得最终每个查询结果的和尽可能地大。小蓝想知道相比原数组, 所有查询结果的总和最多可以增加多少?

输入格式

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

第二行包含 $n$ 个整数 $A_{1}, A_{2}, \cdots, A_{n}$ , 相邻两个整数之间用一个空格分隔。

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

接下来 $m$ 行, 每行包含两个整数 $L_{i} 、 R_{i}$ , 相邻两个整数之间用一个空格分隔。

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

原来的和为 $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 n$。