Le royaume JOI compte $N$ villes, numérotées de $1$ à $N$. La ville $1$ est la capitale. Chaque ville possède une valeur appelée animation ; la valeur initiale de l'animation de la ville $i$ ($1 \le i \le N$) est $C_i$.

Une route du royaume JOI relie deux villes distinctes dans les deux sens. Initialement, le royaume JOI ne possède aucune route. Vous avez prévu $N-1$ constructions de routes. La $j$-ième construction ($1 \le j \le N-1$) doit se dérouler de la manière suivante.

• Deux villes, $A_j$ et $B_j$, sont désignées, de sorte qu'en utilisant uniquement les routes construites à ce moment-là, il est possible d'aller de la ville $1$ à la ville $A_j$, mais impossible d'aller de la ville $1$ à la ville $B_j$.
• Vous construisez une route reliant la ville $A_j$ à la ville $B_j$. Le coût de cette construction est le nombre de paires de villes $(s,t)$ satisfaisant les conditions suivantes :

Les villes $s$ et $t$ se trouvent sur le plus court chemin entre la ville $1$ et la ville $A_j$ ; lorsqu'on va de la ville $1$ à la ville $A_j$, on atteint la ville $s$ avant la ville $t$ ; et la valeur de l'animation de la ville $s$ est strictement supérieure à celle de la ville $t$.

Ici, les villes situées sur le chemin entre la ville $1$ et la ville $A_j$ incluent la ville $1$ et la ville $A_j$. Remarquez que le plus court chemin entre la ville $1$ et la ville $A_j$ est unique.

• Les valeurs de l'animation de toutes les villes situées sur le chemin entre la ville $1$ et la ville $A_j$ deviennent égales à la valeur de l'animation de la ville $B_j$.

Vous souhaitez connaître le coût de chaque construction.

Tâche

Étant données les informations sur les villes et les constructions de routes, écrivez un programme qui calcule le coût de chaque construction.

Entrée

Lisez les données suivantes sur l'entrée standard.

• La première ligne de l'entrée contient un entier $N$. Cela signifie que le royaume JOI compte $N$ villes.
• La deuxième ligne de l'entrée contient $N$ entiers séparés par des espaces, $C_1,C_2,\ldots,C_N$. Cela signifie que la valeur initiale de l'animation de la ville $i$ ($1 \le i \le N$) est $C_i$.
• La $j$-ième ligne ($1 \le j \le N-1$) des $N-1$ lignes suivantes contient deux entiers séparés par un espace, $A_j,B_j$. Cela signifie que les villes $A_j$ et $B_j$ sont désignées pour la $j$-ième construction de route.

Sortie

Écrivez $N-1$ lignes sur la sortie standard. La $j$-ième ligne ($1 \le j \le N-1$) de la sortie contient le coût de la $j$-ième construction de route.

Contraintes

Toutes les données d'entrée satisfont les conditions suivantes.

• $1 \le N \le 100\,000$.
• $1 \le C_i \le 1\,000\,000\,000$ ($1 \le i \le N$).
• $1 \le A_j \le N$ ($1 \le j \le N-1$).
• $1 \le B_j \le N$ ($1 \le j \le N-1$).
• En utilisant les routes construites avant la $j$-ième construction, il est possible d'aller de la ville $1$ à la ville $A_j$, mais impossible d'aller de la ville $1$ à la ville $B_j$ ($1 \le j \le N-1$).

Sous-tâches

Il y a 3 sous-tâches. Les scores et les contraintes supplémentaires de chaque sous-tâche sont les suivants :

Sous-tâche 1 [7 points]

• $N \le 500$.

Sous-tâche 2 [9 points]

• $N \le 4000$.

Sous-tâche 3 [84 points]

Il n'y a aucune contrainte supplémentaire.

Exemples

Entrée 1

5
1 2 3 4 5
1 2
2 3
2 4
3 5

Sortie 1

0
0
0
2

Remarque

Dans l'exemple d'entrée 1, les constructions se déroulent comme suit :

• Lors de la première construction, aucune paire $(s,t)$ ne satisfait les conditions, donc le coût est $0$. Une route reliant les villes $1$ et $2$ est construite, et la valeur de l'animation de la ville $1$ devient $2$.
• Lors de la deuxième construction, aucune paire $(s,t)$ ne satisfait non plus les conditions, donc le coût est $0$. Une route reliant les villes $2$ et $3$ est construite, et les valeurs de l'animation des villes $1$ et $2$ deviennent $3$.
• Lors de la troisième construction, aucune paire $(s,t)$ ne satisfait non plus les conditions, donc le coût est $0$. Une route reliant les villes $2$ et $4$ est construite, et les valeurs de l'animation des villes $1$ et $2$ deviennent $4$.
• Lors de la quatrième construction, deux paires $(s,t)=(1,3),(2,3)$ satisfont les conditions, donc le coût est $2$. Une route reliant les villes $3$ et $5$ est construite, et les valeurs de l'animation des villes $1$, $2$ et $3$ deviennent $5$.

Entrée 2

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

Sortie 2

0
0
0
1
1
0
1
2
3