Hay un árbol (grafo conexo acíclico no dirigido) compuesto por $N$ vértices. Los vértices están numerados del $1$ al $N$, y las aristas están numeradas del $1$ al $N-1$. Cada vértice tiene un peso.

Escriba un programa que procese las siguientes consultas:

• u v: Imprima el número de pesos distintos de los vértices en el camino desde $u$ hasta $v$.

Entrada

La primera línea contiene un entero $N$ ($2 \le N \le 100{,}000$).

La segunda línea contiene los pesos de los vértices en orden desde el vértice $1$ hasta el $N$.

Las siguientes $N-1$ líneas contienen dos enteros $u$ y $v$ que representan los extremos de la arista $i$.

La siguiente línea contiene un entero $M$ ($1 \le M \le 100{,}000$), el número de consultas.

Las siguientes $M$ líneas contienen cada una una consulta.

Los pesos de los vértices son números naturales menores o iguales a $1{,}000{,}000$.

Salida

Imprima los resultados de cada consulta en orden, uno por línea.

Ejemplos

Entrada 1

8
105 2 9 3 8 5 7 7
1 2
1 3
1 4
3 5
3 6
3 7
4 8
2
2 5
7 8

Salida 1

4
4