MathJax.Hub.Config({ tex2jax: { inlineMath: [["$","$"], ["\\(","\\)"]], processEscapes: true }}); blockquote { font-family: Menlo, Monaco, "Courier New", monospace; color: #333333; display: block; padding: 8.5px; margin: 0 0 9px; font-size: 12px; line-height: 18px; background-color: #f5f5f5; border: 1px solid #ccc; border: 1px solid rgba(0, 0, 0, 0.15); -webkit-border-radius: 4px; -moz-border-radius: 4px; border-radius: 4px; white-space: pre; white-space: pre-wrap; word-break: break-all; word-wrap: break-word; }

Problem Statement

JAG Company is a sweatshop (sweatshop is called "burakku kigyo" in Japanese), and you are the CEO for the company.

You are planning to determine $N$ employees' salary as low as possible (employees are numbered from $1$ to $N$). Each employee's salary amount must be a positive integer greater than zero. At that time, you should pay attention to the employees' contribution degree. If the employee $i$'s contribution degree $c\_i$ is greater than the employee $j$'s contribution degree $c\_j$, the employee $i$ must get higher salary than the employee $j$'s salary. If the condition is not satisfied, employees may complain about their salary amount.

However, it is not necessarily satisfied in all pairs of the employees, because each employee can only know his/her close employees' contribution degree and salary amount. Therefore, as long as the following two conditions are satisfied, employees do not complain to you about their salary amount.

• If the employees $i$ and $j$ are close to each other, $c\_i < c\_j \\Leftrightarrow p\_i < p\_j$ must be satisfied, where $p\_i$ is the employee $i$'s salary amount.
• If the employee $i$ is close to the employees $j$ and $k$, $c\_j < c\_k \\Leftrightarrow p\_j < p\_k$ must be satisfied.

Write a program that computes the minimum sum of all employees' salary amount such that no employee complains about their salary.

Input

Each input is formatted as follows:

$N$
$c\_1$ ... $c\_N$
$M$
$a\_1$ $b\_1$
...
$a\_M$ $b\_M$

The first line contains an integer $N$ ($1 \\le N \\le100{,}000$), which indicates the number of employees. The second line contains $N$ integers $c\_i$ ($1 \\leq c\_i \\leq 100{,}000$) representing the contribution degree of employee $i$.

The third line contains an integer $M$ ($0 \\leq M \\leq 200{,}000$), which specifies the number of relationships. Each of the following $M$ lines contains two integers $a\_i$ and $b\_i$ ($a\_i \\neq b\_i$, $1 \\leq a\_i, b\_i \\leq N$). It represents that the employees $a\_i$ and $b\_i$ are close to each other. There is no more than one relationship between each pair of the employees.

Output

Print the minimum sum of all employees' salary amounts in a line.

Sample Input 1

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

### Output for the Sample Input 1

```plain
5```

* * *

### Sample Input 2

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

### Output for the Sample Input 2

```plain
6```

* * *

### Sample Input 3

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

### Output for the Sample Input 3

```plain
4```

* * *

### Sample Input 4

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

### Output for the Sample Input 4

```plain
10```

* * *

### Sample Input 5

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

### Output for the Sample Input 5

```plain
13```

* * *