#include <bits/stdc++.h>   using namespace std;   long long M = 1e9 + 7;   const long long N = 1e6 + 7;   long long a[N];   long long n;   long long res = 0;   long long par[N];   long long sz[N];   long long findpar(long long v) {     if (par[v] == v) return v;     return par[v] = findpar(par[v]);   }   int32_t main() {     ios::sync_with_stdio(0);     cin.tie(0);     cout.tie(0);     cin >> n;     for (long long i = 1; i <= n; i++) {       cin >> a[i];       par[i] = i;       sz[i] = 1;     }     vector<pair<long long, pair<long long, long long> > > vec;     for (long long i = 1; i < n; i++) {       long long v, u;       cin >> v >> u;       vec.push_back({max(a[v], a[u]), {v, u}});     }     sort(vec.begin(), vec.end());     for (auto pr : vec) {       long long x = pr.first;       long long v = findpar(pr.second.first);       long long u = findpar(pr.second.second);       res += sz[v] * sz[u] * x;       par[v] = u;       sz[u] += sz[v];     }     for (long long i = 0; i < vec.size(); i++)       vec[i].first = -1 * (min(a[vec[i].second.first], a[vec[i].second.second]));     sort(vec.begin(), vec.end());     for (long long i = 1; i <= n; i++) {       par[i] = i;       sz[i] = 1;     }     for (auto pr : vec) {       long long x = pr.first;       long long v = findpar(pr.second.first);       long long u = findpar(pr.second.second);       res += sz[v] * sz[u] * x;       par[v] = u;       sz[u] += sz[v];     }     cout << res;   }   