F. Несбалансированность дерева
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Задано дерево T, состоящее из n вершин. На каждой вершине записано число; на i-й — ai. Определим функцию I(x, y) — разница между максимальным и минимальным значением ai на простом пути между вершинами x и y.

Ваша задача — вычислить .

Входные данные

В первой строке записано одно целое число n (1 ≤ n ≤ 106) — количество вершин в дереве.

Во второй строке записаны n целых чисел a1, a2, ..., an (1 ≤ ai ≤ 106) — числа, записанные на вершинах.

Затем задана n - 1 строка. В каждой записано по два целых числа x и y, задающие ребро между вершинами x и y (1 ≤ x, y ≤ n, x ≠ y). Гарантируется, что данные ребра формируют дерево.

Выходные данные

Выведите одно число — .

Пример
Входные данные
4
2 2 3 1
1 2
1 3
1 4
Выходные данные
6