En el reino de JOI hay $N$ ciudades, numeradas del $1$ al $N$. La ciudad $1$ es la capital. Cada ciudad tiene un valor llamado vitalidad, y el valor inicial de vitalidad de la ciudad $i$ ($1 \le i \le N$) es $C_i$.

Una carretera del reino de JOI conecta dos ciudades distintas en ambos sentidos. Al principio no hay ninguna carretera en el reino de JOI. Has planificado la construcción de $N-1$ carreteras. La construcción $j$ ($1 \le j \le N-1$) se realizará de la siguiente manera:

• Se designan dos ciudades, $A_j$ y $B_j$, de modo que, utilizando solo las carreteras construidas hasta ese momento, se pueda ir de la ciudad $1$ a la ciudad $A_j$, pero no de la ciudad $1$ a la ciudad $B_j$.
• Construyes una carretera que conecta las ciudades $A_j$ y $B_j$. El coste de esta construcción es el número de parejas de ciudades $(s,t)$ que cumplen las siguientes condiciones:

Las ciudades $s$ y $t$ se encuentran en el camino más corto entre las ciudades $1$ y $A_j$; al ir de la ciudad $1$ a la ciudad $A_j$, se llega a la ciudad $s$ antes que a la ciudad $t$; y el valor de vitalidad de la ciudad $s$ es estrictamente mayor que el de la ciudad $t$.

Aquí, las ciudades que se encuentran en el camino entre las ciudades $1$ y $A_j$ incluyen tanto la ciudad $1$ como la ciudad $A_j$. Ten en cuenta que el camino más corto entre las ciudades $1$ y $A_j$ es único.

• Los valores de vitalidad de todas las ciudades del camino entre las ciudades $1$ y $A_j$ pasan a ser iguales al valor de vitalidad de la ciudad $B_j$.

Quieres conocer el coste de cada construcción.

Tarea

Dados los datos de las ciudades y de las construcciones de carreteras, escribe un programa que calcule el coste de cada construcción.

Entrada

Lee los siguientes datos de la entrada estándar.

• La primera línea de la entrada contiene un entero $N$. Esto significa que hay $N$ ciudades en el reino de JOI.
• La segunda línea de la entrada contiene $N$ enteros separados por espacios, $C_1,C_2,\ldots,C_N$. Esto significa que el valor inicial de vitalidad de la ciudad $i$ ($1 \le i \le N$) es $C_i$.
• La línea $j$ ($1 \le j \le N-1$) de las siguientes $N-1$ líneas contiene dos enteros separados por un espacio, $A_j,B_j$. Esto significa que las ciudades $A_j$ y $B_j$ se designan para la construcción de carretera $j$.

Salida

Escribe $N-1$ líneas en la salida estándar. La línea $j$ ($1 \le j \le N-1$) debe contener el coste de la construcción de carretera $j$.

Restricciones

Todos los datos de entrada cumplen las siguientes condiciones.

• $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$).
• Utilizando las carreteras construidas antes de la construcción $j$, se puede ir de la ciudad $1$ a la ciudad $A_j$, pero no de la ciudad $1$ a la ciudad $B_j$ ($1 \le j \le N-1$).

Subtareas

Hay 3 subtareas. La puntuación y las restricciones adicionales de cada una son las siguientes:

Subtarea 1 [7 puntos]

• $N \le 500$.

Subtarea 2 [9 puntos]

• $N \le 4000$.

Subtarea 3 [84 puntos]

No hay restricciones adicionales.

Ejemplos

Entrada 1

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

Salida 1

0
0
0
2

Nota

En la entrada de ejemplo 1, las construcciones se realizan de la siguiente manera:

• En la primera construcción no hay ninguna pareja $(s,t)$ que cumpla las condiciones, por lo que el coste es $0$. Se construye una carretera que conecta las ciudades $1$ y $2$, y el valor de vitalidad de la ciudad $1$ pasa a ser $2$.
• En la segunda construcción tampoco hay ninguna pareja $(s,t)$ que cumpla las condiciones, por lo que el coste es $0$. Se construye una carretera que conecta las ciudades $2$ y $3$, y los valores de vitalidad de las ciudades $1$ y $2$ pasan a ser $3$.
• En la tercera construcción tampoco hay ninguna pareja $(s,t)$ que cumpla las condiciones, por lo que el coste es $0$. Se construye una carretera que conecta las ciudades $2$ y $4$, y los valores de vitalidad de las ciudades $1$ y $2$ pasan a ser $4$.
• En la cuarta construcción, las dos parejas $(s,t)=(1,3),(2,3)$ cumplen las condiciones, por lo que el coste es $2$. Se construye una carretera que conecta las ciudades $3$ y $5$, y los valores de vitalidad de las ciudades $1$, $2$ y $3$ pasan a ser $5$.

Entrada 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

Salida 2

0
0
0
1
1
0
1
2
3