#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define maxn 100010
#define LEFT 0
#define RIGHT 1
#define pii pair<int, int>
int N;
struct node {
node *ch[2];
node *par;
node *pp; //path pointer
int sz;
int val; //store the current value, is passed with path pointer
int key; //just for debugging purposes, store the index for the node
node(int vv, int kk) : val(vv), key(kk) { //sets default values
ch[LEFT] = NULL;
ch[RIGHT] = NULL;
pp = NULL;
par = NULL;
sz = 1;
}
bool isroot() {
return !par || par->ch[LEFT] != this && par->ch[RIGHT] != this;
}
void update() { //really only does update stuff
sz = 1;
if (ch[LEFT]) {
ch[LEFT]->par = this; //why not
sz += ch[LEFT]->sz;
}
if (ch[RIGHT]) {
ch[RIGHT]->par = this;
sz += ch[RIGHT]->sz;
}
}
int getDirection() {
if (par == NULL) return -1;
if (this == par->ch[LEFT]) return LEFT;
if (this == par->ch[RIGHT]) return RIGHT;
return -1;
}
void setChild(int dir, node * c) {
ch[dir] = c;
if (c) c->par = this;
}
void rotateup() {
int dir = getDirection();
node *p = par;
if (!p->isroot()) {
p->par->ch[p->getDirection()] = this;
}
par = p->par;
node *pMid = ch[!dir];
p->setChild(dir, pMid);
setChild(!dir, p);
pp = p->pp;
p->pp = NULL;
val = p->val;
p->update();
update();
}
};
node *nc[maxn]; //just store some nodes b/c why not
vector<pii> cstuff; //used for counting inversions
void splay(node * x) {
//all updates for splay should be covered in rotateup()
x->update();
while (!x->isroot()) {
x->update();
node *p1 = x->par;
if (!p1->isroot()) {
node *g = p1->par;
if (p1->getDirection() == x->getDirection()) {
p1->rotateup(); //zig zig
}
else x->rotateup(); // zig zag
}
x->rotateup();
}
}
void access(node *x) {
x->update();
splay(x);
if (x->ch[RIGHT]) {
x->ch[RIGHT]->val = x->val;
x->ch[RIGHT]->pp = x; //cut it off
x->ch[RIGHT]->par = NULL;
}
x->ch[RIGHT] = NULL;
x->update();
// cout << "my stuff: " << x->sz << endl;
cstuff.push_back(pii(x->val, x->sz));
while (x->pp) { //not at root of tree of aux trees yet
node *w = x->pp;
splay(w);
if (w->ch[RIGHT]) {
w->ch[RIGHT]->val = w->val;
w->ch[RIGHT]->pp = w;
w->ch[RIGHT]->par = NULL;
}
w->ch[RIGHT] = NULL; //temporary for our purposes
w->update();
// cout << "key line: " << w->key << " " << w->val << " " << w->sz << endl;
cstuff.push_back(pii(w->val, w->sz));
w->ch[RIGHT] = x;
x->par = w;
x->pp = NULL;
splay(x);
}
}
int seg[maxn*4];
int nums[maxn]; //the number stored for each guy
//set up segment tree stuff
int BIT[maxn];
void update(int spot, int diff) {
while (spot <= N) {
// cout << "u spot: " << spot << endl;
BIT[spot] += diff;
spot += spot & (-spot);
}
}
int query(int spot) {
int ans = 0;
while (spot > 0) {
// cout << "spot: " << spot << endl;
ans += BIT[spot];
spot -= spot & (-spot);
}
return ans;
}
/*
void up(int spot, int diff, int ss, int se, int si) {
if (spot < ss || spot > se) return;
if (ss == se) {
seg[si] += diff;
return;
}
int mid = (ss+se)/2;
up(spot, diff, ss, mid, si*2+1);
up(spot, diff, mid+1, se, si*2+2);
seg[si] = seg[si*2+1] + seg[si*2+2];
}
void update(int spot, int diff) {
up(spot, diff, 0, N, 0);
}
int qu(int qs, int qe, int ss, int se, int si) {
if (qs > qe || ss > se || qs > se || qe < ss) return 0;
if (qs <= ss && se <= qe) {
return seg[si];
}
int mid = (ss+se)/2;
return qu(qs, qe, ss, mid, si*2+1) +
qu(qs, qe, mid+1, se, si*2+2);
}
int query(int qs, int qe) {
return qu(qs, qe, 0, N, 0);
}
*/
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> N;
set<int> seen;
map<int, int> encode; //for compression
//process each edge in order
for (int i = 1; i <= N; i++) {
cin >> nums[i];
seen.insert(nums[i]);
}
int cv = 0;
for (int cur : seen) {
encode[cur] = ++cv; //want 1-indexed
}
for (int i = 1; i <= N; i++) {
nums[i] = encode[nums[i]];
nc[i] = new node(nums[i], i);
//cout << "oval: " << nc[i]->val << endl;
}
fill(BIT, BIT+maxn, 0);
int a, b;
for (int i = 0; i < N-1; i++) {
cin >> a >> b; //read in edges in order
cstuff.clear();
ll ans = 0LL;
access(nc[a]); //access this first guy
//now the things in cstuff should be good to go
//time to calculate the answer
//reverse(cstuff.begin(), cstuff.end());
for (pii cur : cstuff) {
int curval = cur.first;
int amount = cur.second;
// cout << "something on the list: " << curval << " in count of " << amount << endl;
ans += amount*1LL*query(curval-1); //want amount greater than me
update(cur.first, cur.second);
}
for (pii cur : cstuff) {
update(cur.first, 0-cur.second);
}
nc[b]->pp = nc[a];
access(nc[b]); //run a classic access now,
// this should augment my value up real nice
nc[b]->val = nums[b]; //set the thing straight now
cout << ans << '\n';
}
cin >> N;
}
//use ll b/c i think we might need it
