블랙 기업

JAG Company는 착취 기업(착취 기업은 일본어로 "burakku kigyo"라고 부른다)이고, 당신은 이 회사의 CEO다.

당신은 $N$명의 직원(직원은 $1$부터 $N$까지 번호가 붙어 있다)의 급여를 최대한 낮게 정하려고 한다. 각 직원의 급여는 0보다 큰 양의 정수여야 한다. 이때 직원의 기여도에 주의해야 한다. 직원 $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$가 서로 가깝다는 뜻이다. 각 직원 쌍 사이에 존재하는 관계는 최대 하나다.

전체 직원 급여 합의 최솟값을 한 줄에 출력한다.