JAG 公司是一家血汗工厂（日语中称为“burakku kigyo”），你是该公司的 CEO。

你计划尽可能降低 $N$ 名员工的工资（员工编号从 $1$ 到 $N$）。每名员工的工资必须是大于零的正整数。在制定工资时，你需要考虑员工的贡献度。如果员工 $i$ 的贡献度 $c_i$ 大于员工 $j$ 的贡献度 $c_j$，那么员工 $i$ 的工资必须高于员工 $j$ 的工资。如果该条件未得到满足，员工可能会对他们的工资数额提出不满。

然而，这一条件并不一定需要在所有员工对之间都满足，因为每名员工只能了解到与其关系密切的员工的贡献度和工资数额。因此，只要满足以下两个条件，员工就不会对工资数额提出不满：

• 如果员工 $i$ 和 $j$ 关系密切，则必须满足 $c_i < c_j \iff p_i < p_j$，其中 $p_i$ 是员工 $i$ 的工资数额。
• 如果员工 $i$ 与员工 $j$ 和 $k$ 均关系密切，则必须满足 $c_j < c_k \iff p_j < p_k$。

编写一个程序，计算在没有员工对工资提出不满的前提下，所有员工工资总额的最小值。

输入格式

第一行包含一个整数 $N$ ($1 \le N \le 10^5$)，表示员工人数。第二行包含 $N$ 个整数 $c_i$ ($1 \le c_i \le 10^5$)，表示员工 $i$ 的贡献度。

第三行包含一个整数 $M$ ($0 \le M \le 2 \cdot 10^5$)，表示关系的数量。接下来的 $M$ 行，每行包含两个整数 $a_i$ 和 $b_i$ ($a_i \neq b_i, 1 \le a_i, b_i \le 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