408315: GYM103092 A Alternate

BThero живет в богатой прекрасной стране — Демиляндии. Демиляндия представляет собой сеть из $$$n$$$ городов и $$$n-1$$$ двусторонних дорог между ними. Гарантируется, что из любого города можно попасть в любой другой по этим дорогам.

BThero учится в университете на программиста. Первый курс для него закончился успешно, теперь он хочет летом подработать немного денег. Он смог подсчитать для каждого города значение $$$p_i$$$ — сколько долларов он сможет заработать в $$$i$$$-м городе. Получилось так, что массив $$$p$$$ состоит из различных целых чисел от $$$1$$$ до $$$n$$$.

BThero еще не бывал в большинстве городов своей страны. Поэтому он решил убить двух зайцев одним выстрелом — он выберет себе маршрут, который начинается в произвольном городе $$$a$$$, заканчивается в произвольном городе $$$b > a$$$ и не проходит через один город дважды. По пути он будет одновременно подрабатывать в городах.

Однако ситуация с программистами в стране не очень простая. В некоторых городах он может легко заработать крупную сумму денег, а в некоторых ему придется экономить на расходах. От этого напрямую зависит его настроение. Если в городе непосредственно до нынешнего он заработал $$$x$$$ денег, а в нынешнем заработает $$$y < x$$$, то его настроение будет плохим. Соответственно, если $$$y > x$$$, его настроение будет хорошим.

Назовем запоминающимся маршрут, вдоль которого у BThero настроение будет изменяться каждый раз. Примеры его доходов в запоминающихся маршрутах: $$$[2, 5, 1, 4]$$$, $$$[3, 1, 2]$$$, $$$[1, 2]$$$. Заметим, что маршруты из двух городов тоже являются запоминающимися.

Он еще не запланировал свой маршрут, но для интересной жизни хочет чтобы маршрут был запоминающимся. Помогите ему найти общее количество таких маршрутов!

В первой строке входного файла дано одно целое число $$$n$$$ — количество городов в Демиляндии ($$$1 \le n \le 200000$$$). Во второй строке следуют $$$n$$$ целых чисел $$$p_1$$$, ..., $$$p_n$$$ — его подсчитанный доход в каждом городе ($$$1 \le p_i \le n$$$, $$$p_i \neq p_j$$$ для всех $$$i \neq j$$$). Следующие $$$n-1$$$ строк содержат пары различных целых чисел $$$a$$$, $$$b$$$ — номера городов, соединенных очередной дорогой ($$$1 \le a, b \le n$$$, $$$a \neq b$$$).

Выведите одно единственное целое число — количество запоминающихся маршрутов.

4
3 2 1 4
1 2
2 3
2 4

4

Все запоминающиеся маршруты из примера:

• $$$a = 1$$$, $$$b = 2$$$.
• $$$a = 1$$$, $$$b = 4$$$.
• $$$a = 2$$$, $$$b = 3$$$.
• $$$a = 2$$$, $$$b = 4$$$.