Ci sono $N$ città nel Regno di JOI, numerate da $1$ a $N$. La città $1$ è la capitale. Ogni città ha un valore chiamato vivacità e il valore iniziale di vivacità della città $i$ ($1 \le i \le N$) è $C_i$.

Una strada nel Regno di JOI collega due città diverse in modo bidirezionale. Inizialmente non c'è alcuna strada nel Regno di JOI. Hai pianificato $N-1$ costruzioni di strade. La $j$-esima costruzione ($1 \le j \le N-1$) è pianificata nel modo seguente.

• Vengono designate due città, $A_j$ e $B_j$, tali che in quel momento è possibile andare dalla città $1$ alla città $A_j$ e non è possibile andare dalla città $1$ alla città $B_j$ usando solo le strade già costruite.

• Costruisci una strada che collega la città $A_j$ e la città $B_j$. Il costo di questa costruzione è il numero di coppie di città $(s,t)$ che soddisfano le seguenti condizioni:

  La città $s$ e la città $t$ si trovano sul cammino minimo tra la città $1$ e la città $A_j$, andando dalla città $1$ alla città $A_j$ si arriva alla città $s$ prima che alla città $t$, e il valore di vivacità della città $s$ è strettamente maggiore di quello della città $t$.

  Qui, le città che si trovano sul cammino tra la città $1$ e la città $A_j$ includono la città $1$ e la città $A_j$. Si noti che il cammino minimo tra la città $1$ e la città $A_j$ è unico.

• I valori di vivacità di tutte le città che si trovano sul cammino tra la città $1$ e la città $A_j$ cambiano assumendo il valore di vivacità della città $B_j$.

Vuoi conoscere il costo di ciascuna costruzione.

Compito

Dati i dati delle città e delle costruzioni delle strade, scrivi un programma che calcoli il costo di ciascuna costruzione.

Formato di input

Leggi i seguenti dati dallo standard input.

• La prima riga dell'input contiene un intero $N$. Ciò significa che ci sono $N$ città nel Regno di JOI.
• La seconda riga dell'input contiene $N$ interi separati da spazi $C_1, C_2, \cdots C_N$. Ciò significa che il valore iniziale di vivacità della città $i$ ($1 \le i \le N$) è $C_i$.
• La $j$-esima riga ($1 \le j \le N-1$) delle successive $N-1$ righe contiene due interi separati da spazio $A_j$, $B_j$. Ciò significa che la città $A_j$ e la città $B_j$ sono designate per la $j$-esima costruzione di strada.

Formato di output

Scrivi $N-1$ righe sullo standard output. La $j$-esima riga ($1 \le j \le N-1$) dell'output contiene il costo della $j$-esima costruzione di strada.

Vincoli

Tutti i dati di input soddisfano le seguenti condizioni.

• $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$).
• Usando le strade costruite prima della $j$-esima costruzione, è possibile andare dalla città $1$ alla città $A_j$ e non è possibile andare dalla città $1$ alla città $B_j$ ($1 \le j \le N-1$).

Sottoproblemi

Ci sono 3 sottoproblemi. Il punteggio e i vincoli aggiuntivi di ciascun sottoproblema sono i seguenti:

Sottoproblema 1 [7 punti]

• $N \le 500$.

Sottoproblema 2 [9 punti]

• $N \le 4000$.

Sottoproblema 3 [84 punti]

Non ci sono vincoli aggiuntivi.

Esempi

Input 1

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

Output 1

0
0
0
2

Nota

Nell'Input di esempio 1, le costruzioni vengono effettuate come segue:

• Nella prima costruzione, non ci sono coppie $(s,t)$ che soddisfano le condizioni, quindi il costo è $0$. Viene costruita una strada che collega la città $1$ e la città $2$ e il valore di vivacità della città $1$ cambia in $2$.
• Anche nella seconda costruzione non ci sono coppie $(s,t)$ che soddisfano le condizioni, quindi il costo è $0$. Viene costruita una strada che collega la città $2$ e la città $3$ e i valori di vivacità della città $1$ e della città $2$ cambiano in $3$.
• Anche nella terza costruzione non ci sono coppie $(s,t)$ che soddisfano le condizioni, quindi il costo è $0$. Viene costruita una strada che collega la città $2$ e la città $4$ e i valori di vivacità della città $1$ e della città $2$ cambiano in $4$.
• Nella quarta costruzione, due coppie $(s,t)=(1,3),(2,3)$ soddisfano le condizioni, quindi il costo è $2$. Viene costruita una strada che collega la città $3$ e la città $5$ e i valori di vivacità della città $1$, della città $2$ e della città $3$ cambiano in $5$.

Input 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

Output 2

0
0
0
1
1
0
1
2
3