#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
struct Edge {
  int u, v, w;
  bool operator<(const Edge &e) const { return w < e.w; }
};
Edge e[N];
int f[N], siz[N];
inline int find(int x) { return f[x] == x ? x : f[x] = find(f[x]); };
inline void merge(int x, int y) {
  int fx = find(x), fy = find(y);
  if (fx == fy) return;
  if (siz[fx] < siz[fy])
    f[fx] = fy, siz[fy] += siz[fx];
  else
    f[fy] = fx, siz[fx] += siz[fy];
}
int a[N];
int n;
int main() {
  int i, u, v;
  scanf("%d", &n);
  for (i = 1; i <= n; i++) scanf("%d", a + i);
  for (i = 1; i < n; i++)
    scanf("%d%d", &u, &v), e[i] = (Edge){u, v, max(a[u], a[v])};
  long long res = 0;
  sort(e + 1, e + n);
  for (i = 1; i <= n; i++) f[i] = i, siz[i] = 1;
  for (i = 1; i < n; i++)
    res += 1ll * e[i].w * siz[find(e[i].u)] * siz[find(e[i].v)],
        merge(e[i].u, e[i].v);
  for (i = 1; i < n; i++) e[i].w = max(-a[e[i].u], -a[e[i].v]);
  sort(e + 1, e + n);
  for (i = 1; i <= n; i++) f[i] = i, siz[i] = 1;
  for (i = 1; i < n; i++)
    res += 1ll * e[i].w * siz[find(e[i].u)] * siz[find(e[i].v)],
        merge(e[i].u, e[i].v);
  printf("%I64d\n", res);
  return 0;
}
