#include <bits/stdc++.h> 

using namespace std;

typedef long long ll;

const int N = (int)1e5 + 12, MOD = (int)1e9 + 7;

int n, pr[N], c[N], sum = 0;

void make() {
    vector<int> cl;
    for(int i = 1; i <= n; i++) {
        cl.push_back(c[i]);
    }
    sort(cl.begin(), cl.end());
    cl.resize(unique(cl.begin(), cl.end()) - cl.begin());
    for(int i = 1; i <= n; i++) {
        c[i] = lower_bound(cl.begin(), cl.end(), c[i]) - cl.begin() + 1;
    }
}
int t[N];
void add(int pos, int val) {
    while(pos <= n ) {
        t[pos] += val;
        pos += pos & -pos;
    }
}
int get(int i) {
    int ret = 0;
    while(i) {
        ret += t[i];
        i -= i & -i;
    }
    return ret;
}
int get(int l, int r) {
    return get(r) - get(l - 1);
}
void test() {
    cin >> n;
    for(int i = 1; i <= n; i++) {
        cin >> c[i];
    }
    make();
    for(int i = 1; i <= n - 1; i++) {
        int a, b;
        cin >> a >> b;
        pr[b] = a;
        vector<int> x;
        while(a) {
            x.push_back(a);
            a = pr[a];
        }
        reverse(x.begin(), x.end());
        int res = 0, m = (int)x.size();
        for(int j = 0; j < m; j++) {
            res += get(c[x[j]] + 1, n);
            add(c[x[j]], 1);
            if(!j) {
                sum++;
            } else if(c[x[j]] != c[x[j] - 1]) {
                sum++;
            }
        }
        assert(sum <= n * 8);
        for(int j : x) {
            add(c[j], -1);
        }
        for(int j : x) {
            c[j] = c[b];
        }
        cout << res << '\n';
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int t = 1;
    // cin >> t;

    while(t--) 
        test();

    return 0;
}