← 返回题目列表

AtCoder · icpc2015summer_day4_j

J. 黑色公司

中文机器翻译题面 查看原题

问题陈述

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