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

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

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

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

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

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