$N$ sommets d'un arbre (graphe connexe non orienté sans cycle) sont donnés. Les sommets sont numérotés de $1$ à $N$, et les arêtes de $1$ à $N-1$. Chaque sommet a un poids.

Écrivez un programme qui effectue la requête suivante.

• u v : Afficher le nombre de poids distincts des sommets sur le chemin de $u$ à $v$.

Entrée

La première ligne contient $N$ ($2 \le N \le 100\,000$).

La deuxième ligne contient les poids des sommets dans l'ordre du sommet $1$ au sommet $N$.

Les $N-1$ lignes suivantes contiennent les deux sommets $u$ et $v$ reliés par l'arête $i$.

La ligne suivante contient le nombre de requêtes $M$ ($1 \le M \le 100\,000$).

Les $M$ lignes suivantes contiennent une requête par ligne.

Les poids des sommets sont toujours des entiers naturels inférieurs ou égaux à $1\,000\,000$.

Sortie

Pour chaque requête, afficher le résultat sur une ligne, dans l'ordre.

Exemples

Entrée 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

Sortie 1

4
4