题目描述

给你一个长度为 $n$ 的数列 $a_1, a_2, \ldots, a_n$ 以及 $m$ 个下标区间。

第 $i$ 个下标区间表示为 $[l_i, r_i]$。

要求从数列 $a$ 中选择一些数，在满足如下条件的情况下，你所选择这些数的数值之和最小：

每一个下标区间内都有至少一个你选择的数。

即：对于任意一个下标区间 $[l_i, r_i]$，都至少存在一个下标 $p$ 满足你选择了 $a_p$ 且 $l_i \le p \le r_i$。

输入格式

第一行，一个整数 $n(1 \le n \le 2 \cdot 10^5)$。

第二行，$n$ 个整数 $a_1, a_2, \ldots, a_n(1 \le a_i \le 10^9)$，以空格分隔。

第三行，一个整数 $m(1 \le m \le 2 \cdot 10^5)$。

接下来 $m$ 行，每行包含两个整数 $l_i$ 和 $r_i$，以一个空格分隔（$1 \le l_i \le r_i \le n$）。

输出格式

输出一个整数，表示答案。即：在每个区间都包含至少一个选择的数字的情况下，你选择的这些数字的最小总和。

样例

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

5

说明/提示

样例解释

最有解释选择下标 $1$ 和 $4$，$a_1 + a_4 = 1 + 4 = 5$。

数据规模与约定

• 对于 $20\%$ 的数据，$n,m \le 20, a_i \le 100$
• 对于 $50\%$ 的数据，$n,m \le 2000, a_i \le 10^5$
• 对于 $100\%$ 的数据，$1 \le n,m \le 2 \cdot 10^5, 1 \le a_i \le 10^9$