Black Company

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

You are planning to set the salaries of $N$ employees as low as possible (employees are numbered from $1$ to $N$). Each employee's salary must be a positive integer greater than zero. You must also pay attention to each employee's contribution degree. If employee $i$'s contribution degree $c\_i$ is greater than employee $j$'s contribution degree $c\_j$, employee $i$ must receive a higher salary than employee $j$. If this condition is not satisfied, employees may complain about their salaries.

However, this does not have to hold for every pair of employees, because each employee can only know the contribution degrees and salaries of the employees close to them. Therefore, employees do not complain about their salaries as long as the following two conditions hold.

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

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

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 \le 100{,}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$). This means that employees $a\_i$ and $b\_i$ are close to each other. There is at most one relationship between each pair of employees.

Print the minimum sum of all employees' salaries on one line.