#include <bits/stdc++.h>   using namespace std;   template <typename X>   void MA(X &a, X b) {     a = max(a, b);   }   template <typename X>   void MI(X &a, X b) {     a = min(a, b);   }   int DEBUG = 0, MULTI = 0, GCJ = 0;   struct solver_t;   solver_t *solver;   struct solver_t {     vector<int> A;     vector<vector<int> > EDG;     struct lcu_t {       int N;       vector<int> CNT, PAR;       lcu_t(int N) : N(N) {         PAR.resize(N);         CNT.resize(N);         for (int64_t i = (0); i < (N); ++i) PAR[i] = i;         for (int64_t i = (0); i < (N); ++i) CNT[i] = 1;       }       int parent(int i) {         if (PAR[i] == i)           return i;         else           return PAR[i] = parent(PAR[i]);       }       int64_t get_cnt(int64_t x) { return x * (x - 1) / 2; }       int64_t join(int a, int b) {         int pa = parent(a), pb = parent(b);         if (pa == pb) return 0;         if (!(CNT[pb] >= CNT[pa])) swap(pa, pb);         int64_t diff = -get_cnt(CNT[pa]) - get_cnt(CNT[pb]);         PAR[pa] = pb;         CNT[pb] += CNT[pa];         diff += get_cnt(CNT[pb]);         return diff;       }     };     void solve() {       int N;       cin >> N;       A.resize(N + 1);       for (int64_t i = (1); i <= (N); ++i) cin >> A[i];       EDG.resize(N + 1);       for (int64_t i = (0); i < (N - 1); ++i) {         int X, Y;         cin >> X >> Y;         EDG[X].push_back(Y);         EDG[Y].push_back(X);       }       vector<array<int64_t, 2> > order;       for (int64_t i = (1); i <= (N); ++i) order.push_back({A[i], i});       sort((order).begin(), (order).end());       int64_t res[2] = {};       for (int64_t mode = (0); mode < (2); ++mode) {         lcu_t lcu(N + 1);         int64_t prev_cnt = 0;         int64_t &sum = res[mode];         vector<int> vis(N + 1);         for (int i = 0; i < (int)order.size();) {           int64_t diff = 0;           int j;           {             if (DEBUG)               cerr << 81 <<                        <<                         <<                        <<    << endl;           };           for (j = i; j < (int)order.size(); j++) {             if (order[i][0] != order[j][0]) break;             int u = order[j][1];             vis[u] = 1;             {               if (DEBUG)                 cerr << 86 <<                          <<   vis   << u                       <<                          <<  vis   << u << endl;             };             for (int v : EDG[u])               if (vis[v]) {                 diff += lcu.join(u, v);                 {                   if (DEBUG)                     cerr << 90 <<                              <<  u <<     << v <<     << diff                           <<     << u <<     << v <<     << diff << endl;                 };               }           }           {             if (DEBUG)               cerr << 93 <<                        <<  order[i][0] <<     << diff                     <<     << order[i][0] <<     << diff << endl;           };           sum += order[i][0] * diff;           prev_cnt += diff;           i = j;         }         reverse((order).begin(), (order).end());         {           if (DEBUG)             cerr << 99 <<                      <<  sum                   <<     << sum << endl;         };         {           if (DEBUG)             cerr << 100 <<                      <<   !!                    <<                      <<  !!  << endl;         };       }       cout << abs(res[0] - res[1]) <<   n ;     }     void gen() {}     void brute() {}   };   int main(int argc, char **argv) {     for (int64_t i = (1); i <= (argc - 1); ++i)       for (int j = 0; argv[i][j]; j++)         if (argv[i][j] ==  . ) freopen(argv[i],  r , stdin);     for (int64_t i = (1); i <= (argc - 1); ++i)       if (argv[i] == string( q )) DEBUG = 1 << 30;     for (int64_t i = (1); i <= (argc - 1); ++i)       if (argv[i] == string( gen )) {         (solver = new solver_t())->gen();         exit(0);       }     for (int64_t i = (1); i <= (argc - 1); ++i)       if (argv[i] == string( brute )) {         (solver = new solver_t())->brute();         exit(0);       }     ios::sync_with_stdio(false), cin.tie(0);     cout.setf(ios::fixed), cout.precision(10);     int t;     if (MULTI || GCJ)       cin >> t;     else       t = 1;     for (int64_t i = (1); i <= (t); ++i) {       if (DEBUG) cerr << 129 <<     << i << endl;       if (GCJ) cout <<  Case #  << i <<  :  ;       solver = new solver_t();       solver->solve();     }     return 0;   }   