// Code by Parsa Eslami
#include <bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define FORR(i,a,b) for(int i=a;i>=b;i--)
#define maxm(a,b) a=max(a,b)
#define minm(a,b) a=min(a,b)
#define all(x) x.begin(),x.end()
#define SZ(x) ((int)x.size())
#define bit(i,j) ((j>>i)&1)
#define pb push_back
#define lc 2*id
#define rc 2*id+1
#define dmid int mid=(r+l)/2
#define err(x) cerr<#x<<" : "<<x<<'\n'
#define F first
#define S second
using namespace std;
const int N=4000+4;
int par[N],val[N];
struct fenwick{
int fen[N];
void add(int k,int x){
while(k>0){
fen[k]+=x;
k-=(k&(-k));
}
}
int get(int k){
int rt=0;
while(k<N){
rt+=fen[k];
k+=(k&(-k));
}
return rt;
}
};
fenwick fen;
int Get(){
int x; cin>>x; return x;
}
void Set(int v,int x){
val[v]=x;
if(v==1) return;
Set(par[v],x);
}
ll get(int u){
ll rt=0;
int v=u;
vector<int> vc;
while(1){
vc.pb(v);
if(v==1) break;
v=par[v];
}
reverse(all(vc));
for(int x:vc){
rt+=fen.get(val[x]+1);
fen.add(val[x],+1);
}
for(int x:vc) fen.add(val[x],-1);
return rt;
}
int32_t main(){
iostream::sync_with_stdio(0); cin.tie(0);
int n=Get();
FOR(i,1,n) val[i]=Get();
vector<pii> vc;
FOR(i,1,n) vc.pb({val[i],i});
sort(all(vc)); int x0=0;
FOR(i,0,SZ(vc)-1){
if(i==0||vc[i].F!=vc[i-1].F) x0++;
val[vc[i].S]=x0;
}
FOR(i,1,n-1){
int u=Get(),v=Get();
cout<<get(u)<<'\n';
par[v]=u;
Set(u,val[v]);
}
return 0;
}
