У королівстві 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$, але не можна дістатися з міста $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 є $N$ міст.
- Другий рядок містить $N$ цілих чисел $C_1,C_2,\ldots,C_N$, розділених пробілами. Це означає, що початкове значення жвавості міста $i$ ($1 \le i \le N$) дорівнює $C_i$.
- Рядок з номером $j$ ($1 \le j \le N-1$) серед наступних $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$, але не можна дістатися з міста $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
Пояснення
У першому прикладі будівництва відбуваються так:
- Під час першого будівництва немає пар $(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