트리의 Imbalance Value

n개의 정점으로 이루어진 트리 T가 주어진다. 각 정점에는 수가 하나씩 적혀 있으며, 정점 i에 적힌 수는 ai이다. 정점 x와 y를 잇는 단순 경로에서 ai의 최댓값과 최솟값의 차이를 함수 I(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). 이 간선들이 트리를 이룬다는 것이 보장된다.

와 같은 수 하나를 출력한다.