29122번 - Домашнее задание 다국어

Линн уже взрослая, скоро она пойдет в колледж. Но поступить туда не так просто. Она решила прорешивать задачи старых лет, чтобы лучше подготовиться.

Одним из заданий на вступительной олимпиаде прошлого года была следующая задача: дано дерево, в котором в $i$-й вершине записано число $a_i$. Все, что требовалось от участников олимпиады --- посчитать сумму $$\sum_{i=1}^n \sum_{j=i}^n (max(i \ldots j)-min(i \ldots j)) \cdot len(i \ldots j)$$

Здесь $max(i \ldots j)$ --- максимальное из значений $a_k$ для всех вершин $k$ на пути из $i$ в $j$, $min(i \ldots j)$ --- минимальное из тех же значений, $len(i \ldots j)$ --- число вершин на пути из $i$ в $j$.

Линн уже который час пытается решить эту задачу, но все безуспешно. Помогите ей!

В первой строке входного файла записано целое число $n$ ($1 \le n \le 5 \cdot 10^4$) --- число вершин в дереве. Во второй строке заданы $n$ целых чисел $a_i$ ($0 \le a_i \le 10^5$) --- числа, записанные в вершинах. В следующих $n-1$ строках заданы пары целых чисел $u, v$ ($1 \le u, v \le n$) --- ребра дерева.

В единственной строке выходного файла выведите значение искомой суммы.