#include <bits/stdc++.h>
using namespace std;
int f[1000100], vis[1000100];
pair<int, int> p[1000100];
void Union(int a, int b) {
  int t = f[a] + f[b];
  if (f[a] > f[b]) swap(a, b);
  f[a] = t;
  f[b] = a;
}
int root(int u) { return f[u] < 0 ? u : (f[u] = root(f[u])); }
int n, a[1000100];
vector<int> e[1000100];
long long SolveMax() {
  long long ans = 0;
  for (int i = 1; i <= n; ++i) {
    vis[i] = 0;
    f[i] = -1;
    p[i] = pair<int, int>(a[i], i);
  }
  sort(p + 1, p + n + 1);
  for (int i = 1; i <= n; ++i) {
    int u = p[i].second;
    vis[u] = 1;
    for (int v : e[u])
      if (vis[v]) {
        int ru = root(u);
        int rv = root(v);
        ans += 1ll * f[ru] * f[rv] * p[i].first;
        Union(ru, rv);
      }
  }
  return ans;
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  ;
  cin >> n;
  for (int i = 1; i <= n; ++i) cin >> a[i];
  for (int i = 2; i <= n; ++i) {
    int u, v;
    cin >> u >> v;
    e[u].push_back(v);
    e[v].push_back(u);
  }
  long long ans = SolveMax();
  for (int i = 1; i <= n; ++i) a[i] = -a[i];
  ans += SolveMax();
  cout << ans;
}
