JOI 王國有 $N$ 個城市，編號由 $1$ 至 $N$。城市 $1$ 係首都。每個城市都有一個叫做活力值嘅數值，城市 $i$（$1 \le i \le N$）最初嘅活力值係 $C_i$。

JOI 王國嘅每條道路都雙向連接兩個唔同嘅城市。最初，JOI 王國冇任何道路。你計劃咗進行 $N-1$ 次道路建設。第 $j$ 次建設（$1 \le j \le N-1$）會按以下方式進行。

• 指定兩個城市 $A_j$ 同 $B_j$。只利用當時已經建好嘅道路，可以由城市 $1$ 去到城市 $A_j$，但去唔到城市 $B_j$。
• 你會建造一條連接城市 $A_j$ 同城市 $B_j$ 嘅道路。今次建設嘅費用，就係符合以下條件嘅城市對 $(s,t)$ 數目：

城市 $s$ 同城市 $t$ 都喺城市 $1$ 到城市 $A_j$ 嘅最短路徑上；由城市 $1$ 去城市 $A_j$ 時，會先到達城市 $s$，再到達城市 $t$；而城市 $s$ 嘅活力值嚴格大過城市 $t$ 嘅活力值。

呢度，城市 $1$ 到城市 $A_j$ 嘅路徑上嘅城市，包括城市 $1$ 同城市 $A_j$。留意城市 $1$ 到城市 $A_j$ 嘅最短路徑係唯一嘅。

• 城市 $1$ 到城市 $A_j$ 嘅路徑上所有城市嘅活力值，都會改成城市 $B_j$ 嘅活力值。

你想知道每次建設嘅費用。

任務

俾定城市同道路建設嘅資料，請寫一個程式，計出每次建設嘅費用。

輸入格式

由標準輸入讀取以下資料。

• 輸入第一行包含一個整數 $N$，表示 JOI 王國有 $N$ 個城市。
• 輸入第二行包含 $N$ 個以空格分隔嘅整數 $C_1,C_2,\ldots,C_N$，表示城市 $i$（$1 \le i \le N$）最初嘅活力值係 $C_i$。
• 之後 $N-1$ 行嘅第 $j$ 行（$1 \le j \le N-1$）包含兩個以空格分隔嘅整數 $A_j,B_j$，表示第 $j$ 次道路建設指定嘅城市係城市 $A_j$ 同城市 $B_j$。

輸出格式

向標準輸出寫出 $N-1$ 行。輸出第 $j$ 行（$1 \le j \le N-1$）包含第 $j$ 次道路建設嘅費用。

數據範圍

所有輸入資料都符合以下條件。

• $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$）。
• 只利用第 $j$ 次建設之前已經建好嘅道路，可以由城市 $1$ 去到城市 $A_j$，但去唔到城市 $B_j$（$1 \le j \le N-1$）。

子任務

一共有 3 個子任務。各個子任務嘅分數同額外限制如下：

子任務 1［7 分］

• $N \le 500$。

子任務 2［9 分］

• $N \le 4000$。

子任務 3［84 分］

冇額外限制。

樣例

輸入格式 1

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

輸出格式 1

0
0
0
2

說明

喺輸入樣例 1，建設會按以下方式進行：

• 第一次建設中，冇城市對 $(s,t)$ 符合條件，所以費用係 $0$。建造一條連接城市 $1$ 同城市 $2$ 嘅道路，城市 $1$ 嘅活力值改成 $2$。
• 第二次建設中，同樣冇城市對 $(s,t)$ 符合條件，所以費用係 $0$。建造一條連接城市 $2$ 同城市 $3$ 嘅道路，城市 $1$ 同城市 $2$ 嘅活力值改成 $3$。
• 第三次建設中，同樣冇城市對 $(s,t)$ 符合條件，所以費用係 $0$。建造一條連接城市 $2$ 同城市 $4$ 嘅道路，城市 $1$ 同城市 $2$ 嘅活力值改成 $4$。
• 第四次建設中，兩對城市 $(s,t)=(1,3),(2,3)$ 符合條件，所以費用係 $2$。建造一條連接城市 $3$ 同城市 $5$ 嘅道路，城市 $1$、城市 $2$ 同城市 $3$ 嘅活力值改成 $5$。

輸入格式 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

輸出格式 2

0
0
0
1
1
0
1
2
3