Há $N$ cidades no Reino JOI, numeradas de $1$ a $N$. A cidade 1 é a capital. Cada cidade tem um valor chamado vitalidade, e o valor inicial da vitalidade da cidade $i$ ($1\le i\le N$) é $C_i$.

Uma estrada no Reino JOI liga duas cidades diferentes nos dois sentidos. Inicialmente, não há estradas no Reino JOI. Você planejou $N-1$ construções de estradas. A construção de número $j$ ($1\le j\le N-1$) está planejada da seguinte forma.

• São indicadas duas cidades, $A_j$ e $B_j$, sendo possível ir da cidade 1 à cidade $A_j$, mas não à cidade $B_j$, usando apenas as estradas já construídas naquele momento.

• Você constrói uma estrada que liga a cidade $A_j$ à cidade $B_j$. O custo dessa construção é o número de pares de cidades $(s,t)$ que satisfazem as seguintes condições:

  As cidades $s$ e $t$ estão no caminho mais curto entre a cidade 1 e a cidade $A_j$; ao ir da cidade 1 à cidade $A_j$, chega-se à cidade $s$ antes da cidade $t$; e a vitalidade da cidade $s$ é estritamente maior que a da cidade $t$.

  Aqui, as cidades no caminho entre a cidade 1 e a cidade $A_j$ incluem a cidade 1 e a cidade $A_j$. Observe que o caminho mais curto entre a cidade 1 e a cidade $A_j$ é único.

• Os valores de vitalidade de todas as cidades no caminho entre a cidade 1 e a cidade $A_j$ mudam para o valor de vitalidade da cidade $B_j$.

Você quer saber o custo de cada construção.

Tarefa

Dados os dados das cidades e das construções de estradas, escreva um programa que calcule o custo de cada construção.

Entrada

Leia os seguintes dados da entrada padrão.

• A primeira linha contém um inteiro $N$. Isso significa que há $N$ cidades no Reino JOI.
• A segunda linha contém $N$ inteiros separados por espaços, $C_1,C_2,\ldots,C_N$. Isso significa que o valor inicial de vitalidade da cidade $i$ ($1\le i\le N$) é $C_i$.
• A linha de número $j$ ($1\le j\le N-1$) das $N-1$ linhas seguintes contém dois inteiros separados por um espaço, $A_j,B_j$. Isso significa que as cidades $A_j$ e $B_j$ são indicadas para a construção de estrada de número $j$.

Saída

Escreva $N-1$ linhas na saída padrão. A linha de número $j$ ($1\le j\le N-1$) deve conter o custo da construção de estrada de número $j$.

Restrições

Todos os dados de entrada satisfazem as seguintes condições.

• $1\le N\le100\,000$.
• $1\le C_i\le1\,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$).
• Usando as estradas construídas antes da construção de número $j$, é possível ir da cidade 1 à cidade $A_j$, mas não da cidade 1 à cidade $B_j$ ($1\le j\le N-1$).

Subtarefas

Há 3 subtarefas. A pontuação e as restrições adicionais de cada uma são as seguintes:

Subtarefa 1 [7 pontos]

• $N\le500$.

Subtarefa 2 [9 pontos]

• $N\le4000$.

Subtarefa 3 [84 pontos]

Não há restrições adicionais.

Exemplos

Entrada 1

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

Saída 1

0
0
0
2

Nota

No exemplo de entrada 1, as construções são realizadas da seguinte forma:

• Na primeira construção, não há pares $(s,t)$ que satisfaçam as condições, portanto o custo é $0$. É construída uma estrada que liga a cidade 1 à cidade 2, e a vitalidade da cidade 1 muda para $2$.
• Na segunda construção, também não há pares $(s,t)$ que satisfaçam as condições, portanto o custo é $0$. É construída uma estrada que liga a cidade 2 à cidade 3, e os valores de vitalidade das cidades 1 e 2 mudam para $3$.
• Na terceira construção, também não há pares $(s,t)$ que satisfaçam as condições, portanto o custo é $0$. É construída uma estrada que liga a cidade 2 à cidade 4, e os valores de vitalidade das cidades 1 e 2 mudam para $4$.
• Na quarta construção, dois pares, $(s,t)=(1,3),(2,3)$, satisfazem as condições, portanto o custo é $2$. É construída uma estrada que liga a cidade 3 à cidade 5, e os valores de vitalidade das cidades 1, 2 e 3 mudam para $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

Saída 2

0
0
0
1
1
0
1
2
3