问题描述

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 \le 100{,}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

```plain
5```

* * *

### 示例输入 2

```plain
3
1 2 3
2
1 2
1 3```

### 示例输出 2

```plain
6```

* * *

### 示例输入 3

```plain
4
1 1 2 2
2
1 2
3 4```

### 示例输出 3

```plain
4```

* * *

### 示例输入 4

```plain
5
1 2 5 5 1
6
1 2
4 1
2 3
5 2
4 3
4 5 ```

### 示例输出 4

```plain
10```

* * *

### 示例输入 5

```plain
6
4 3 2 1 5 3
7
4 2
1 5
2 6
6 5
4 1
1 6
6 3```

### 示例输出 5

```plain
13```