Matcom Online Grader

Fito es el CEO de una nueva compañía de desarrollo de software que se llama Foogle.

Él quiere determinar los salarios de los $N$ programadores de la empresa de forma tal que estos sean lo menor posible. Cada salario debe ser una cantidad entera positiva y se debe tener en cuenta el factor de contribución de cada programador. Si el factor de contribución $c_i$ del programador $i$ es mayor que el factor de contribución $c_j$ del programador $j$, entonces el salario de $i$ debe ser mayor que el salario de $j$. Si esto no se cumple puede que se creen discusiones entre los programadores.

Sin embargo, esto no se tiene que cumplir para todos los pares de programadores, porque cada programador solo puede saber el factor de contribución de programadores que sean cercanos a él. Así que resumiendo, solo habrá discusiones si se incumple algunas de las siguientes condiciones:

• Si el programador $i$ y el $j$ son cercanos entonces $c_i<c_j \Longleftrightarrow p_i < p_j$, donde $p_i$ es el salario del programador $i$-esimo.
• Si el empleado $i$ es cercano a los empleados $j$ y $k$ entonces $c_j < c_k \Longleftrightarrow p_j < p_k$.

Su tarea es escribir un programa que dados los factores de contribución de cada uno de los empleados calcule la menor suma posible de todos los salarios de forma tal que no haya ninguna discusión.

Input

La primera línea de entrada tendrá un entero con la cantidad de programadores de la empresa $N (1 \leq N \leq 100 000)$. La segunda línea tendrá $N$ enteros $c_i (1 \leq c_i \leq 100000)$ separados por un espacio que representan los factores de contribución. La tercera línea contiene un entero $M (0 \leq M \leq 200000)$ que indica la cantidad de relaciones. Cada una de las siguientes $M$ líneas contiene dos enteros $a$ y $b (a \neq b, 1 \leq a,b \leq N)$, que indican que los programadores $a$ y $b$ son cercanos. No hay más de una relación entre el mismo par de programadores.

Output

Un entero con la menor suma posible de los salarios.

Sample test(s)