#include <bits/stdc++.h>
using namespace std;
namespace fastIO {
bool IOerror = 0;
inline char nc() {
  static char buf[100000], *p1 = buf + 100000, *pend = buf + 100000;
  if (p1 == pend) {
    p1 = buf;
    pend = buf + fread(buf, 1, 100000, stdin);
    if (pend == p1) {
      IOerror = 1;
      return -1;
    }
  }
  return *p1++;
}
inline bool blank(char ch) {
  return ch == ' ' || ch == '\n' || ch == '\r' || ch == '\t';
}
inline long long read() {
  bool sign = 0;
  char ch = nc();
  long long x = 0;
  for (; blank(ch); ch = nc())
    ;
  if (IOerror) return 0;
  if (ch == '-') sign = 1, ch = nc();
  for (; ch >= '0' && ch <= '9'; ch = nc()) x = x * 10 + ch - '0';
  if (sign) x = -x;
  return x;
}
};  // namespace fastIO
using namespace fastIO;
struct node {
  long long v;
  long double dis;
  bool operator<(const node& b) const {
    if (dis == b.dis) return v > b.v;
    return dis > b.dis;
  }
  node(long long x, long double y) {
    v = x;
    dis = y;
  }
};
struct edge {
  long long v, nex;
} e[2500010];
struct f {
  long long num, id;
} d[1000010];
long long first[1000010], eid = 0, n, fa[1000010], faa[1000010], siz[1000010],
                          vis[1000010], ans = 0;
void addedge(long long u, long long v) {
  e[++eid].v = v;
  e[eid].nex = first[u];
  first[u] = eid;
}
bool cmp(f d1, f d2) {
  if (d1.num != d2.num) return d1.num < d2.num;
  return d1.id > d2.id;
}
bool cmp1(f d1, f d2) {
  if (d1.num != d2.num) return d1.num > d2.num;
  return d1.id > d2.id;
}
long long find(long long x) { return x == faa[x] ? x : faa[x] = find(faa[x]); }
signed main() {
  memset(first, -1, sizeof(first));
  n = read();
  for (long long i = 1; i <= n; i++) {
    d[i].num = read(), d[i].id = i;
  }
  for (long long i = 1; i < n; i++) {
    long long x = read(), y = read();
    addedge(x, y);
    addedge(y, x);
  }
  sort(d + 1, d + 1 + n, cmp);
  for (long long i = 1; i <= n; i++) faa[i] = i, siz[i] = 1;
  for (long long i = 1; i <= n; i++) {
    long long u = d[i].id;
    vis[u] = 1;
    for (long long j = first[u]; j + 1; j = e[j].nex) {
      long long v = e[j].v;
      if (vis[v]) {
        ans += siz[u] * siz[find(v)] * d[i].num;
        siz[u] += siz[find(v)];
        faa[find(v)] = u;
      }
    }
  }
  memset(vis, 0, sizeof(vis));
  sort(d + 1, d + 1 + n, cmp1);
  for (long long i = 1; i <= n; i++) faa[i] = i, siz[i] = 1;
  for (long long i = 1; i <= n; i++) {
    long long u = d[i].id;
    vis[u] = 1;
    for (long long j = first[u]; j + 1; j = e[j].nex) {
      long long v = e[j].v;
      if (vis[v]) {
        ans -= siz[u] * siz[find(v)] * d[i].num;
        siz[u] += siz[find(v)];
        faa[find(v)] = u;
      }
    }
  }
  cout << ans;
  return 0;
}
