JOI Kingdom 有 $N$ 座城市，編號為 $1$ 到 $N$。城市 $1$ 是首都。每座城市都有一個稱為繁榮度的數值，城市 $i$（$1 \le i \le N$）的初始繁榮度為 $C_i$。

JOI Kingdom 的道路雙向連接兩座不同的城市。最初，JOI Kingdom 沒有任何道路。你計畫進行 $N-1$ 次道路建設。第 $j$ 次建設（$1 \le j \le N-1$）將按以下方式進行。

• 指定兩座城市 $A_j$ 和 $B_j$，此時僅使用當時已建成的道路，可以從城市 $1$ 到達城市 $A_j$，但無法從城市 $1$ 到達城市 $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 Kingdom 有 $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$，表示城市 $A_j$ 和城市 $B_j$ 被指定用於第 $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$，但無法從城市 $1$ 到達城市 $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