#include <string.h>
#include <stdio.h>
#include <time.h>
#include <stdlib.h>
void reverse(int *a, int l, int r)
{
for (int temp = --r; l < r; ++l, --r)
temp = a[l], a[l] = a[r], a[r] = temp;
}
void sort(int *a, int l, int r)
{
while (l < r)
{
int i = l, j = l, k = r, t, p = a[l + rand()%(r-l)];
while (j < k)
{
if (a[j] == p) ++j;
else if (a[j] < p) t = a[i], a[i] = a[j], a[j] = t, ++i, ++j;
else t = a[--k], a[k] = a[j], a[j] = t;
}
sort(a, l, i);
l = k;
}
}
#define N 100000
#define M (2*N)
#define L 17
int n, c[N], tin[N], hld[N], dd[N], sz[N], par[N], c2[N];
int *eh[N], eo[N], *eh_[N], eo_[N];
long long fw[N], cost;
void fwadd(int p, long long k)
{
for (; p < N; p |= p + 1) fw[p] += k;
}
long long fwsum(int p)
{
long long z = 0;
for (; p > 0; p &= p - 1) z += fw[p-1];
return z;
}
int vv[N*L], vo;
void inversions()
{
for (int j = 0; j < vo; j += 2)
fwadd(vv[j+1], vv[j]),
cost += vv[j] * fwsum(vv[j+1]);
for (int j = 0; j < vo; j += 2)
fwadd(vv[j+1], -vv[j]);
}
void push(int **eh, int *eo, int i, int j)
{
int o = eo[i]++;
if (!o) eh[i] = (int*)realloc(eh[i], 2*sizeof**eh);
else if (!(o&o-1)) eh[i] = (int*)realloc(eh[i], 2*sizeof**eh*o);
eh[i][o] = j;
}
void dfs1(int u, int p)
{
par[u] = p;
sz[u] = 1;
for (int v, j = 0; j < eo[u]; ++j) if ((v = eh[u][j]) != p)
{
dd[v] = dd[u] + 1;
dfs1(v, u);
sz[u] += sz[v];
if (eh[u][0] == p || sz[v] > sz[eh[u][0]])
eh[u][j] = eh[u][0], eh[u][0] = v;
}
}
void pushchain(int i, int j, int k)
{
if (eo_[i] >= 2 && eh_[i][eo_[i]-2] == j)
eh_[i][eo_[i]-1] += k;
else
push(eh_, eo_, i, j),
push(eh_, eo_, i, k);
}
void dfs2(int u, int p)
{
static int timer = 0;
tin[u] = timer++;
for (int v, j = 0; j < eo[u]; ++j) if ((v = eh[u][j]) != p)
hld[v] = (j == 0) ? hld[u] : v,
dfs2(v, u);
pushchain(hld[u], c[u], 1);
}
int main()
{
srand(time(0));
scanf("%d", &n);
for (int i = 0; i < n; ++i)
scanf("%d", c+i);
memcpy(c2, c, sizeof *c2 * n);
sort(c2, 0, n);
for (int i = 0; i < n; ++i)
{
int lower = -1, upper = n;
while (upper - lower > 1)
{
int mid = lower + (upper - lower) / 2;
if (c2[mid] <= c[i])
lower = mid;
else
upper = mid;
}
c[i] = lower;
}
static int ee[N][2];
for (int i = 1, u, v; i < n; ++i)
{
scanf("%d%d", &u, &v);
--u, --v;
ee[i][0] = u;
ee[i][1] = v;
push(eh, eo, u, v);
push(eh, eo, v, u);
}
dfs1(0, -1);
hld[0] = 0;
dfs2(0, 0);
for (int i = 1, u, v; i < n; ++i)
{
u = ee[i][0], v = ee[i][1];
vo = 0;
/* collect all values into vector to find inversions */
for (int ii = u; ii != -1; ii = par[hld[ii]])
{
int take_here = tin[ii] - tin[hld[ii]] + 1, start = vo;
for (int taken = 0, jj = eo_[hld[ii]] - 1; jj >= 0; jj -= 2)
{
int value = eh_[hld[ii]][jj-1], freq = eh_[hld[ii]][jj];
if (freq + taken >= take_here)
freq = take_here - taken, jj = -1;
if (freq)
vv[vo++] = value, vv[vo++] = freq;
taken += freq;
}
reverse(vv, start, vo);
}
cost = 0;
inversions();
printf("%lld\n", cost);
/* change liveliness of all node on 1-u path to liveliness[v] */
for (int ii = u; ii != -1; ii = par[hld[ii]])
{
int take_here = tin[ii] - tin[hld[ii]] + 1;
for (int taken = 0, jj = eo_[hld[ii]] - 1; jj >= 0; jj -= 2, eo_[hld[ii]] -= 2)
{
int freq = eh_[hld[ii]][jj];
if (freq + taken >= take_here)
{
freq = take_here - taken;
eh_[hld[ii]][jj] -= freq;
if (eh_[hld[ii]][jj] == 0)
eo_[hld[ii]] -= 2;
break;
}
taken += freq;
}
pushchain(hld[ii], c[v], take_here);
}
}
}
/* O(n lg^2 n)
* proof like lct */
