В королевстве 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