Im Königreich JOI gibt es $N$ Städte, die von $1$ bis $N$ nummeriert sind. Stadt $1$ ist die Hauptstadt. Jede Stadt besitzt einen Wert namens Lebendigkeit; der anfängliche Wert der Lebendigkeit von Stadt $i$ ($1 \le i \le N$) ist $C_i$.

Eine Straße im Königreich JOI verbindet zwei verschiedene Städte in beiden Richtungen. Anfangs gibt es im Königreich JOI keine Straßen. Du hast $N-1$ Straßenbauvorhaben geplant. Das $j$-te Bauvorhaben ($1 \le j \le N-1$) soll folgendermaßen durchgeführt werden.

• Zwei Städte $A_j$ und $B_j$ werden ausgewählt, wobei man ausschließlich über die zu diesem Zeitpunkt bereits gebauten Straßen von Stadt $1$ nach Stadt $A_j$ gelangen kann, aber nicht von Stadt $1$ nach Stadt $B_j$.

• Du baust eine Straße zwischen Stadt $A_j$ und Stadt $B_j$. Die Kosten dieses Bauvorhabens sind die Anzahl der Städtepaare $(s,t)$, die folgende Bedingungen erfüllen:

  Stadt $s$ und Stadt $t$ liegen auf dem kürzesten Weg zwischen Stadt $1$ und Stadt $A_j$. Wenn man von Stadt $1$ nach Stadt $A_j$ geht, erreicht man Stadt $s$ vor Stadt $t$, und der Wert der Lebendigkeit von Stadt $s$ ist strikt größer als der von Stadt $t$.

  Dabei zählen Stadt $1$ und Stadt $A_j$ zu den Städten auf dem Weg zwischen Stadt $1$ und Stadt $A_j$. Beachte, dass der kürzeste Weg zwischen Stadt $1$ und Stadt $A_j$ eindeutig ist.

• Die Werte der Lebendigkeit aller Städte auf dem Weg zwischen Stadt $1$ und Stadt $A_j$ werden auf den Wert der Lebendigkeit von Stadt $B_j$ gesetzt.

Du möchtest die Kosten jedes Bauvorhabens wissen.

Aufgabe

Schreibe ein Programm, das anhand der Daten der Städte und der Straßenbauvorhaben die Kosten jedes Bauvorhabens berechnet.

Eingabe

Lies die folgenden Daten von der Standardeingabe.

• Die erste Eingabezeile enthält eine ganze Zahl $N$. Dies bedeutet, dass es im Königreich JOI $N$ Städte gibt.
• Die zweite Eingabezeile enthält $N$ durch Leerzeichen getrennte ganze Zahlen $C_1,C_2,\ldots,C_N$. Dies bedeutet, dass der anfängliche Wert der Lebendigkeit von Stadt $i$ ($1 \le i \le N$) gleich $C_i$ ist.
• Die $j$-te Zeile ($1 \le j \le N-1$) der folgenden $N-1$ Zeilen enthält zwei durch Leerzeichen getrennte ganze Zahlen $A_j,B_j$. Dies bedeutet, dass Stadt $A_j$ und Stadt $B_j$ für das $j$-te Straßenbauvorhaben ausgewählt werden.

Ausgabe

Gib $N-1$ Zeilen auf der Standardausgabe aus. Die $j$-te Ausgabezeile ($1 \le j \le N-1$) enthält die Kosten des $j$-ten Straßenbauvorhabens.

Beschränkungen

Alle Eingabedaten erfüllen die folgenden Bedingungen.

• $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$).
• Über die vor dem $j$-ten Bauvorhaben gebauten Straßen kann man von Stadt $1$ nach Stadt $A_j$ gelangen, aber nicht von Stadt $1$ nach Stadt $B_j$ ($1 \le j \le N-1$).

Teilaufgaben

Es gibt 3 Teilaufgaben. Die Punktzahlen und zusätzlichen Beschränkungen jeder Teilaufgabe sind wie folgt:

Teilaufgabe 1 [7 Punkte]

• $N \le 500$.

Teilaufgabe 2 [9 Punkte]

• $N \le 4000$.

Teilaufgabe 3 [84 Punkte]

Es gibt keine zusätzlichen Beschränkungen.

Beispiele

Eingabe 1

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

Ausgabe 1

0
0
0
2

Hinweis

In Eingabe 1 werden die Bauvorhaben folgendermaßen durchgeführt:

• Beim ersten Bauvorhaben gibt es keine Paare $(s,t)$, die die Bedingungen erfüllen; daher betragen die Kosten $0$. Eine Straße zwischen Stadt $1$ und Stadt $2$ wird gebaut, und der Wert der Lebendigkeit von Stadt $1$ wird auf $2$ gesetzt.
• Beim zweiten Bauvorhaben gibt es ebenfalls keine Paare $(s,t)$, die die Bedingungen erfüllen; daher betragen die Kosten $0$. Eine Straße zwischen Stadt $2$ und Stadt $3$ wird gebaut, und die Werte der Lebendigkeit von Stadt $1$ und Stadt $2$ werden auf $3$ gesetzt.
• Beim dritten Bauvorhaben gibt es ebenfalls keine Paare $(s,t)$, die die Bedingungen erfüllen; daher betragen die Kosten $0$. Eine Straße zwischen Stadt $2$ und Stadt $4$ wird gebaut, und die Werte der Lebendigkeit von Stadt $1$ und Stadt $2$ werden auf $4$ gesetzt.
• Beim vierten Bauvorhaben erfüllen die zwei Paare $(s,t)=(1,3),(2,3)$ die Bedingungen; daher betragen die Kosten $2$. Eine Straße zwischen Stadt $3$ und Stadt $5$ wird gebaut, und die Werte der Lebendigkeit von Stadt $1$, Stadt $2$ und Stadt $3$ werden auf $5$ gesetzt.

Eingabe 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

Ausgabe 2

0
0
0
1
1
0
1
2
3