#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
#include <set>
#include <cassert>
#define X first
#define Y second
#define PB push_back
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int LOG = 18;
const int N = 1 << LOG;
const int PERZ = 3 * LOG * LOG * N;
const ll OO = 2e18;
const bool DEB = 0;
struct node {
ll sum, in;
bool prop;
node *l, *r;
node() {}
node(ll sum, ll in, bool prop, node *l = NULL, node *r = NULL) : sum(sum), in(in), prop(prop), l(l), r(r) {}
};
int NEW;
node NEWN[PERZ];
node* get() {
assert(NEW < PERZ);
NEWN[NEW].l = NEWN[NEW].r = NULL;
NEWN[NEW].sum = NEWN[NEW].in = NEWN[NEW].prop = 0;
return &NEWN[NEW++];
}
void merge(node *u, node *v, node *w) {
w->in = u->in + v->in;
w->sum = u->sum + v->sum;
w->prop = 0;
}
void child(node *u) {
if(u->l == NULL) u->l = get();
if(u->r == NULL) u->r = get();
}
node* _update(node *u) {
node* v = get();
v->l = u->l;
v->r = u->r;
v->in = u->sum - u->in;
v->sum = u->sum;
v->prop = u->prop ^ 1;
return v;
}
void propagate(node *u) {
if(!u->prop) return;
assert(u->l != NULL && u->r != NULL);
u->l = _update(u->l);
u->r = _update(u->r);
u->prop = 0;
}
node* update(int l, int r, node *u, int lo = 0, int hi = N) { assert(u != NULL);
if(r <= lo || hi <= l) return u;
if(l <= lo && hi <= r) return _update(u);
propagate(u);
int mi = (lo + hi) / 2;
node *v = get();
v->l = update(l, r, u->l, lo, mi);
v->r = update(l, r, u->r, mi, hi);
merge(v->l, v->r, v);
return v;
}
ll query(int l, int r, node *u, int lo = 0, int hi = N) { assert(u != NULL);
if(r <= lo || hi <= l) return 0;
if(l <= lo && hi <= r) return u->in;
propagate(u);
int mi = (lo + hi) / 2;
return query(l, r, u->l, lo, mi) + query(l, r, u->r, mi, hi);
}
vector<int> C; // DODAJ 0
node* build(int lo = 0, int hi = N) {
node* u = get();
u->prop = 0;
if(lo + 1 == hi) {
u->sum = lo < (int) C.size() - 1 ? (ll) C[lo + 1] * C[lo + 1] - C[lo] * C[lo] : 0;
u->in = 0;
u->l = u->r = NULL;
if(DEB && lo < (int) C.size() - 1) printf("%lld ", u->sum);
return u;
}
int mi = (lo + hi) / 2;
u->l = build(lo, mi);
u->r = build(mi, hi);
merge(u->l, u->r, u);
return u;
}
int n, A[N];
int TO[N];
node* RT[N];
set<int> S[N];
void debug(node *u, bool f = 0, int lo = 0, int hi = N) {
f ^= u != NULL ? u->prop : 0;
if(lo + 1 == hi) {
printf("%d ", (int) f);
return;
}
int mi = (lo + hi) / 2;
debug(u != NULL ? u->l : NULL, f, lo, mi);
debug(u != NULL ? u->r : NULL, f, mi, hi);
}
ll unija(int a, int b, int ind) {
if(S[a].size() < S[b].size()) swap(a, b);
TO[ind] = a;
if(DEB) {
printf("{"); for(int x : S[a]) printf("%d ", x); printf("}\n");
printf("{"); for(int x : S[b]) printf("%d ", x); printf("}\n");
printf(" "); debug(RT[a]);
printf("\n^ "); debug(RT[b]);
}
ll ret = 0;
vector<int> TMP(S[b].begin(), S[b].end());
for(int i = (int) TMP.size() - 1; i >= 0; i -= 2) {
int r = TMP[i], l = i != 0 ? TMP[i - 1] : 0; /// |(l) .... |(r) |(r + 1)
ret += query(l, r, RT[a]);
}
for(int x : TMP) {
RT[a] = update(0, x, RT[a]);
if(S[a].find(x) == S[a].end()) S[a].insert(x);
else S[a].erase(x);
}
if(DEB) {
printf("\n= "); debug(RT[a], 0); printf("\n");
printf("{"); for(int x : S[a]) printf("%d ", x); printf("}\n");
}
return ret;
}
int main() {
C.PB(0);
scanf("%d", &n);
for(int i = 1; i <= n; ++i) {
scanf("%d", A + i);
C.PB(A[i]);
TO[i] = i;
}
sort(C.begin(), C.end());
C.erase(unique(C.begin(), C.end()), C.end());
RT[0] = build();
if(DEB) printf("\n");
for(int i = 1; i <= n; ++i) {
int ind = lower_bound(C.begin(), C.end(), A[i]) - C.begin();
RT[i] = update(0, ind, RT[0]);
S[i].insert(ind);
if(DEB) { debug(RT[i]); printf("\n"); }
}
for(int i = n + 1; i < 2 * n; ++i) {
int a, b; scanf("%d%d", &a, &b);
printf("%lld\n", unija(TO[a], TO[b], i));
if(DEB) printf("~~~\n");
}
return 0;
}