#include<bits/stdc++.h>
#pragma GCC optimize("unroll-loops,no-stack-protector")
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pll;
const ll MOD=1e9+7;
const ll MOD2=998244353;
const ll K=350;
const ld pi=3.14159265359;
const ll INF=(1LL<<40);
#define SQ(i) ((i)*(i))
#define REP(i,n) for(ll i=0;i<n;i++)
#define REP1(i,n) for(ll i=1;i<=n;i++)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define setp setprecision
#define lwb lower_bound
#define SZ(_a) (ll)_a.size()
const int N = 1e5 + 7;
struct LCT {
int f[N], ch[N][2], s[N], z[N], a[N];
#define lc ch[p][0]
#define rc ch[p][1]
#define upd(p) s[p] = s[ch[p][0]] + s[ch[p][1]] + 1
#define get(p) (p == ch[f[p]][1])
#define rev(p) v[p] ^= 1, swap(ch[p][0], ch[p][1])
#define isrt(p) (ch[f[p]][0] != p && ch[f[p]][1] != p)
inline void spd(int p) {
if (z[p]) {
if (lc) a[lc] = z[lc] = z[p];
if (rc) a[rc] = z[rc] = z[p];
z[p] = 0;
}
}
inline void rot(int p) {
int x = f[p], y = f[x], u = get(p), v = get(x), o = isrt(x);
f[ch[p][u^1]] = x, ch[x][u] = ch[p][u^1];
f[x] = p, ch[p][u^1] = x, upd(x), upd(p);
if ((f[p] = y) && !o) ch[y][v] = p;
}
void pre(int p) {
if (!isrt(p)) pre(f[p]);
spd(p);
}
inline void splay(int p) {
pre(p);
for (int x = f[p]; !isrt(p); rot(p), x = f[p])
if (!isrt(x)) rot(get(p) == get(x) ? x : p);
}
inline vector<pll> access(int p) {
vector<pll> ret;
int w = 0;
for (int x = 0; p; p = f[x=p])
splay(p), rc = x, upd(p),
ret.pb(mp(a[p], s[p] - w)), w = s[p];
return ret;
}
inline void link(int p, int x) {
int w = a[x];
splay(p), rc = x, f[x] = p, splay(x), upd(x), a[x] = z[x] = w;
}
} lct;
struct BIT {
vector<ll> c;
inline BIT() {}
inline BIT(int n) { c.resize(n); }
inline void add(ll x, ll k) {
while (x < c.size()) c[x] += k, x += x & -x;
}
inline ll ask(ll x) {
ll k = 0;
while (x) k += c[x], x -= x & -x;
return k;
}
};
int n, a[N];
int main() {
ios_base::sync_with_stdio(0);cin.tie(0);
cin>>n;
for (int i = 1; i <= n; i++) cin>>a[i], lct.a[i] = a[i];
sort(a + 1, a + n + 1);
int t = unique(a + 1, a + n + 1) - (a + 1);
BIT c(t + 1);
for (int i = 1; i <= n; i++)
lct.a[i] = lower_bound(a + 1, a + t + 1, lct.a[i]) - a;
lct.s[1] = 1;
for (int i = 1, x, y; i < n; i++) {
cin>>x>>y;
auto ret = lct.access(x);
ll ans = 0;
for (pll o : ret)
ans += o.se * c.ask(o.fi - 1), c.add(o.fi, o.se);
cout<<ans<<"\n";
for (pll o : ret) c.add(o.fi, -o.se);
lct.link(x, y);
}
return 0;
}
