#include<bits/stdc++.h>
using namespace std;
const int N=1e6+2;
int n,a[N],fa[N],sz[N];
long long ans;
struct edge{int x,y;bool operator<(edge o)const{return max(a[x],a[y])<max(a[o.x],a[o.y]);}}e[N];
int find(int k){return fa[k]==k?k:fa[k]=find(fa[k]);}
void solve(){
	for(int i=1;i<=n;i++)fa[i]=i,sz[i]=1;
	sort(e+1,e+n);
	for(int i=1;i<n;i++){
		int x=find(e[i].x),y=find(e[i].y);
		ans+=(long long)max(a[e[i].x],a[e[i].y])*sz[x]*sz[y];
		fa[x]=y,sz[y]+=sz[x];
	}
}
signed main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i];
	for(int i=1;i<n;i++)cin>>e[i].x>>e[i].y;
	solve();for(int i=1;i<=n;i++)a[i]=-a[i];solve();
	cout<<ans;
}