问题陈述
JAG公司是一家血汗工厂(血汗工厂被称为“burakku kigyo”日语),并且您是公司的首席执行官。
您计划将 $N$ 员工的工资确定为尽可能低的(员工编号从 $1$ 到 $N$)。 每个员工的工资金额必须是大于零的正整数。 这个时候就应该关注员工的贡献程度。 如果员工$i$的贡献度$c_i$大于员工$j$的贡献度$c_j$,则员工$i$的工资必须高于员工$j$的工资。 如果不满足条件,员工可以投诉其工资金额。
但是,并不一定对所有员工都满足,因为每个员工只能知道他/她的亲密员工的贡献程度和工资金额。 因此,只要满足以下两个条件,员工就不会向你抱怨工资数额。
- 如果员工 $i$ 和 $j$ 彼此接近,则必须满足 $c_i < c_j \Leftrightarrow p_i < p_j$,其中 $p_i$ 是员工 $i$ 的工资金额。
- 如果员工 $i$ 与员工 $j$ 和 $k$ 接近,则必须满足 $c_j < c_k \Leftrightarrow p_j < p_k$。
编写一个程序,计算所有员工工资金额的最小总和,以便没有员工抱怨他们的工资。
输入
每个输入的格式如下:
$N$
$c_1$ ... $c_N$
$M$
$a_1$ $b_1$
...
$a_M$ $b_M$
第一行包含一个整数$N$ ($1 \le N \le100{,}000$),表示员工数量。 第二行包含$N$个整数$c_i$ ($1 \leq c_i \leq 100{,}000$),代表员工$i$的贡献度。
第三行包含一个整数 $M$ ($0 \leq M \leq 200{,}000$),它指定关系的数量。 以下$M$ 行中的每一行都包含两个整数$a_i$ 和$b_i$ ($a_i \neq b_i$, $1 \leq a_i, b_i \leq N$)。 它表示员工$a_i$ 和$b_i$ 彼此关系密切。 每对员工之间不存在超过一种关系。
输出
打印一行中所有员工工资金额的最小总和。
示例输入 1
3 1 3 3 2 1 2 1 3
样本输入 1 的输出
5
示例输入 2
3 1 2 3 2 1 2 1 3
样本输入 2 的输出
6
示例输入 3
4 1 1 2 2 2 1 2 3 4
样本输入 3 的输出
4
示例输入 4
5 1 2 5 5 1 6 1 2 4 1 2 3 5 2 4 3 4 5
样本输入 4 的输出
10
示例输入 5
6 4 3 2 1 5 3 7 4 2 1 5 2 6 6 5 4 1 1 6 6 3
样本输入 5 的输出
13