Det finns $N$ städer i JOI-riket, som är numrerade från $1$ till $N$. Stad $1$ är huvudstaden. Varje stad har ett värde som kallas livlighet och det ursprungliga värdet på livligheten för stad $i$ ($1 \le i \le N$) är $C_i$.

En väg i JOI-riket förbinder två olika städer i båda riktningarna. Från början finns det ingen väg i JOI-riket. Du har planerat $N-1$ vägbyggen. Det $j$-te bygget ($1 \le j \le N-1$) planeras att utföras på följande sätt.

• Två städer, $A_j$ och $B_j$, utses, där man kan ta sig från stad $1$ till stad $A_j$ och inte kan ta sig från stad $1$ till stad $B_j$ genom att endast använda de vägar som är byggda vid den tidpunkten.

• Du bygger en väg som förbinder stad $A_j$ och stad $B_j$. Kostnaden för detta bygge är antalet par av städer $(s,t)$ som uppfyller följande villkor:

  Stad $s$ och stad $t$ ligger på den kortaste vägen mellan stad $1$ och stad $A_j$, och när man färdas från stad $1$ till stad $A_j$ anländer man till stad $s$ före stad $t$, samt att livlighetsvärdet för stad $s$ är strikt större än det för stad $t$.

  Här inkluderar städerna som ligger på vägen mellan stad $1$ och stad $A_j$ även stad $1$ och stad $A_j$. Observera att den kortaste vägen mellan stad $1$ och stad $A_j$ är unik.

• Livlighetsvärdena för alla städer som ligger på vägen mellan stad $1$ och stad $A_j$ ändras till livlighetsvärdet för stad $B_j$.

Du vill veta kostnaden för varje bygge.

Uppgift

Givet data om städerna och vägbyggena, skriv ett program som beräknar kostnaden för varje bygge.

Indata

Läs följande data från standard inmatning.

• Den första raden i indata innehåller ett heltal $N$. Detta betyder att det finns $N$ städer i JOI-riket.
• Den andra raden i indata innehåller $N$ mellanslagsseparerade heltal $C_1, C_2, \cdots C_N$. Detta betyder att det ursprungliga livlighetsvärdet för stad $i$ ($1 \le i \le N$) är $C_i$.
• Den $j$-te raden ($1 \le j \le N-1$) av de följande $N-1$ raderna innehåller två mellanslagsseparerade heltal $A_j$, $B_j$. Detta betyder att stad $A_j$ och stad $B_j$ utses för det $j$-te vägbygget.

Utdata

Skriv $N-1$ rader till standard utmatning. Den $j$-te raden ($1 \le j \le N-1$) i utdata ska innehålla kostnaden för det $j$-te vägbygget.

Begränsningar

Alla indata uppfyller följande villkor.

• $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$).
• Genom att använda vägar som byggts före det $j$-te bygget kan man ta sig från stad $1$ till stad $A_j$ och kan inte ta sig från stad $1$ till stad $B_j$ ($1 \le j \le N-1$).

Deluppgifter

Det finns 3 deluppgifter. Poängen och de ytterligare begränsningarna för varje deluppgift är följande:

Deluppgift 1 [7 poäng]

• $N \le 500$.

Deluppgift 2 [9 poäng]

• $N \le 4000$.

Deluppgift 3 [84 poäng]

Det finns inga ytterligare begränsningar.

Exempel

Indata 1

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

Utdata 1

0
0
0
2

Förklaring

I exempelindata 1 utförs byggena enligt följande:

• I det första bygget finns det inga par $(s,t)$ som uppfyller villkoren, så kostnaden är $0$. En väg som förbinder stad $1$ och stad $2$ byggs och livlighetsvärdet för stad $1$ ändras till $2$.
• I det andra bygget finns det inte heller några par $(s,t)$ som uppfyller villkoren, så kostnaden är $0$. En väg som förbinder stad $2$ och stad $3$ byggs och livlighetsvärdena för stad $1$ och stad $2$ ändras till $3$.
• I det tredje bygget finns det inte heller några par $(s,t)$ som uppfyller villkoren, så kostnaden är $0$. En väg som förbinder stad $2$ och stad $4$ byggs och livlighetsvärdena för stad $1$ och stad $2$ ändras till $4$.
• I det fjärde bygget uppfyller två par $(s,t)=(1,3),(2,3)$ villkoren, så kostnaden är $2$. En väg som förbinder stad $3$ och stad $5$ byggs och livlighetsvärdena för stad $1$, stad $2$ och stad $3$ ändras till $5$.

Indata 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

Utdata 2

0
0
0
1
1
0
1
2
3