P9691 [GDCPC 2023] Base Station Construction

中国移动通信集团广东有限公司深圳分公司（以下简称``深圳移动``）于 $1999$ 年正式注册。四年后，广东省大学生程序设计竞赛第一次举办。深圳移动与广东省大学生程序设计竞赛一起见证了广东省计算机行业的兴旺与发展。 在建设通信线路的过程中，信号基站的选址是一个非常关键的问题。某城市从西到东的距离为 $n$ 千米，工程师们已经考察了在从西往东 $1, 2, \cdots, n$ 千米的位置建设基站的成本，分别是 $a_1, a_2, \cdots, a_n$。 为了保证居民的通信质量，基站的选址还需要满足 $m$ 条需求。第 $i$ 条需求可以用一对整数 $l_i$ 和 $r_i$ 表示（$1 \le l_i \le r_i \le n$），代表从西往东 $l_i$ 千米到 $r_i$ 千米的位置之间（含两端）至少需要建设 $1$ 座基站。 作为总工程师，您需要决定基站的数量与位置，并计算满足所有需求的最小总成本。

有多组测试数据。第一行输入一个整数 $T$ 表示测试数据组数，对于每组测试数据： 第一行输入一个整数 $n$（$1 \le n \le 5 \times 10^5$）表示城市从西到东的距离。 第二行输入 $n$ 个整数 $a_1, a_2, \cdots, a_n$（$1 \le a_i \le 10^9$），其中 $a_i$ 表示在从西往东 $i$ 千米的位置建设基站的成本。 第三行输入一个整数 $m$（$1 \le m \le 5 \times 10^5$）表示需求的数量。 对于接下来 $m$ 行，第 $i$ 行输入两个整数 $l_i$ 和 $r_i$（$1 \le l_i \le r_i \le n$）表示从西往东 $l_i$ 千米到 $r_i$ 千米的位置之间（含两端）至少需要建设 $1$ 座基站。 保证所有数据 $n$ 之和与 $m$ 之和均不超过 $5 \times 10^5$。

每组数据输出一行一个整数，表示满足所有需求的最小总成本。 **【样例解释】** 对于第一组样例数据，最优方案是在从西往东 $2$ 千米和 $5$ 千米的位置建设基站。总成本为 $2 + 100 = 102$。 对于第二组样例数据，最优方案是在从西往东 $2$ 千米和 $4$ 千米的位置建设基站。总成本为 $3 + 2 = 5$。

For the first sample test case the optimal solution is to build base stations at $2$ kilometers and $5$ kilometers from west to east. The total cost is $2 + 100 = 102$. For the second sample test case the optimal solution is to build base stations at $2$ kilometers and $4$ kilometers from west to east. The total cost is $3 + 2 = 5$.