Terdapat $N$ kota di Kerajaan JOI, yang diberi nomor dari $1$ hingga $N$. Kota $1$ adalah ibu kota. Setiap kota memiliki nilai yang disebut tingkat keramaian, dan nilai awal tingkat keramaian kota $i$ ($1 \le i \le N$) adalah $C_i$.

Jalan di Kerajaan JOI menghubungkan dua kota berbeda secara dua arah. Pada awalnya, tidak ada jalan di Kerajaan JOI. Kamu telah merencanakan $N-1$ pembangunan jalan. Pembangunan ke-$j$ ($1 \le j \le N-1$) direncanakan dilakukan sebagai berikut.

• Dua kota, $A_j$ dan $B_j$, ditentukan sedemikian sehingga kota $A_j$ dapat dicapai dari kota $1$, sedangkan kota $B_j$ tidak dapat dicapai dari kota $1$, hanya dengan menggunakan jalan yang telah dibangun saat itu.

• Kamu membangun jalan yang menghubungkan kota $A_j$ dan kota $B_j$. Biaya pembangunan ini adalah banyaknya pasangan kota $(s,t)$ yang memenuhi kondisi berikut:

  Kota $s$ dan kota $t$ berada pada jalur terpendek antara kota $1$ dan kota $A_j$; ketika bergerak dari kota $1$ menuju kota $A_j$, kota $s$ dicapai sebelum kota $t$; dan tingkat keramaian kota $s$ lebih besar secara ketat daripada tingkat keramaian kota $t$.

  Di sini, kota-kota pada jalur antara kota $1$ dan kota $A_j$ mencakup kota $1$ dan kota $A_j$. Perhatikan bahwa jalur terpendek antara kota $1$ dan kota $A_j$ bersifat unik.

• Tingkat keramaian semua kota pada jalur antara kota $1$ dan kota $A_j$ berubah menjadi tingkat keramaian kota $B_j$.

Kamu ingin mengetahui biaya setiap pembangunan.

Tugas

Diberikan data kota dan pembangunan jalan, tulislah program yang menghitung biaya setiap pembangunan.

Masukan

Baca data berikut dari masukan standar.

• Baris pertama masukan berisi sebuah bilangan bulat $N$. Ini berarti terdapat $N$ kota di Kerajaan JOI.
• Baris kedua masukan berisi $N$ bilangan bulat $C_1,C_2,\ldots,C_N$ yang dipisahkan oleh spasi. Ini berarti nilai awal tingkat keramaian kota $i$ ($1 \le i \le N$) adalah $C_i$.
• Baris ke-$j$ ($1 \le j \le N-1$) dari $N-1$ baris berikutnya berisi dua bilangan bulat $A_j,B_j$ yang dipisahkan oleh spasi. Ini berarti kota $A_j$ dan kota $B_j$ ditentukan untuk pembangunan jalan ke-$j$.

Keluaran

Tuliskan $N-1$ baris ke keluaran standar. Baris ke-$j$ ($1 \le j \le N-1$) keluaran berisi biaya pembangunan jalan ke-$j$.

Batasan

Semua data masukan memenuhi kondisi berikut.

• $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$).
• Dengan menggunakan jalan yang telah dibangun sebelum pembangunan ke-$j$, kota $A_j$ dapat dicapai dari kota $1$, sedangkan kota $B_j$ tidak dapat dicapai dari kota $1$ ($1 \le j \le N-1$).

Subsoal

Terdapat 3 subsoal. Skor dan batasan tambahan setiap subsoal adalah sebagai berikut:

Subsoal 1 [7 poin]

• $N \le 500$.

Subsoal 2 [9 poin]

• $N \le 4000$.

Subsoal 3 [84 poin]

Tidak ada batasan tambahan.

Contoh

Masukan 1

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

Keluaran 1

0
0
0
2

Penjelasan

Pada Contoh Masukan 1, pembangunan dilakukan sebagai berikut:

• Pada pembangunan pertama, tidak ada pasangan $(s,t)$ yang memenuhi kondisi, sehingga biayanya $0$. Jalan yang menghubungkan kota $1$ dan kota $2$ dibangun, dan tingkat keramaian kota $1$ berubah menjadi $2$.
• Pada pembangunan kedua, juga tidak ada pasangan $(s,t)$ yang memenuhi kondisi, sehingga biayanya $0$. Jalan yang menghubungkan kota $2$ dan kota $3$ dibangun, dan tingkat keramaian kota $1$ serta kota $2$ berubah menjadi $3$.
• Pada pembangunan ketiga, juga tidak ada pasangan $(s,t)$ yang memenuhi kondisi, sehingga biayanya $0$. Jalan yang menghubungkan kota $2$ dan kota $4$ dibangun, dan tingkat keramaian kota $1$ serta kota $2$ berubah menjadi $4$.
• Pada pembangunan keempat, dua pasangan $(s,t)=(1,3),(2,3)$ memenuhi kondisi, sehingga biayanya $2$. Jalan yang menghubungkan kota $3$ dan kota $5$ dibangun, dan tingkat keramaian kota $1$, kota $2$, serta kota $3$ berubah menjadi $5$.

Masukan 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

Keluaran 2

0
0
0
1
1
0
1
2
3