#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define ff first
#define ss second
#define all(a) (a.begin(), a.end())
const int mod = 1e9 + 7;
const int N = 1e5;
int n, c[N+10];
vector<int> g[N+10], group[N+10];
int shortest[N+10];
int par[N+10];
typedef tree<int, null_type, less_equal<int> ,rb_tree_tag, tree_order_statistics_node_update> ordered_set;
signed main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n;
for(int i = 1;i <= n; i++){
cin >> c[i];
shortest[i] = -1;
}
int q = n-1;
shortest[1] = 0;
par[1] = -1;
group[1].push_back(1);
while(q--){
int a, b; cin >> a >> b;
int cost = 0;
ordered_set st;
for(int s : group[a]){
int it = st.order_of_key(c[s] + 1);
cost+= (st.size() - it);
st.insert(c[s]);
}
g[a].push_back(b);
for(int x : group[a]){
group[b].push_back(x);
}
group[b].push_back(b);
if(shortest[b] == -1 or shortest[b] > shortest[a]+1){
shortest[b] = shortest[a] + 1;
par[b] = a;
}
int parent = a;
while(parent != -1){
c[parent] = c[b];
parent = par[parent];
}
cout << cost << '\n';
}
return 0;
}
