You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

在建设通信线路的过程中，信号基站的选址是一个非常关键的问题。某城市从西到东的距离为 $n$千米， 工程师们已经考察了在从西往东 $1,2 \ldots n$ 千米的位置建设基站的成本，分别是 $a_1 , a_2 \ldots a_n$。 为了保证居民的通信质量，基站的选址还需要满足 $m$ 条需求。第 $i$ 条需求可以用一对整数 $l_i$ 和$r_i$,$（1 \le l_i r_i \le n）$,表示 ，代表从西往东 $l_i$千米到 $r_i$ 千米的位置之间（含两端）至少需要建设$1$座基站。 作为总工程师，您需要决定基站的数量与位置，并计算满足所有需求的最小总成本。

输入格式

第一行输入一个整数 $n,（1 \le n \le 5 \times 10^5）$表示城市从西到东的距离。 第二行输入$n$个整数$a_1 ,a_2 ,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$ 座基站。

输出格式

每组数据输出一行一个整数，表示满足所有需求的最小总成本。

样例1

输入

5
3 2 4 1 100
3
1 3
2 4
5 5

输出

102

样例2

输入

5
7 3 4 2 2
3
1 4
2 3
4 5

输出

5

数据分布

$20\%$的样例，$n \le 10 , m \le 5，1 \le a_i \le 100$

$30\%$的样例，$n \le 100 , m \le 50,1 \le a_i \le 100$

另外对于 $10\%$ 的数据，$n \le 100 , m \le 50$,$1 \le a_i \le 100$并且保证区间无重叠。

$100\%$ 的数据，$ n \le 5 \times 10^5 , m \le 5 \times 10^5，1 \le a_i \le 10^9 $