You are given a tree T consisting of n vertices. A number is written on each vertex; the number written on vertex i is a_i. Let's denote the function I(x, y) as the difference between maximum and minimum value of a_i on a simple path connecting vertices x and y.

Your task is to calculate $\text{[math]}$ .

Input

The first line contains one integer number n (1 ≤ n ≤ 10⁶) — the number of vertices in the tree.

The second line contains n integer numbers a₁, a₂, ..., a_n (1 ≤ a_i ≤ 10⁶) — the numbers written on the vertices.

Then n - 1 lines follow. Each line contains two integers x and y denoting an edge connecting vertex x and vertex y (1 ≤ x, y ≤ n, x ≠ y). It is guaranteed that these edges denote a tree.

Output

Print one number equal to $\text{[math]}$ .

Imbalance Value of a Tree

Examples