#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 = LOG * N;
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] - (ll) 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], TMP[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;

	auto it = S[b].begin();
	for(int i = 0; i < S[b].size(); ++i) {
		TMP[i] = *it;
		it = next(it);
	}

	for(int i = (int) S[b].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 i = 0; i < S[b].size(); ++i) {
		int x = TMP[i];
		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;
}