#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 5e5 + 5;
int n, a[N], b[N], res;

void cdq(int l, int r) {
	if (l >= r)
		return;
	int mid = (l + r) >> 1;
	cdq(l, mid);
	cdq(mid + 1, r);
	int i = l, j = mid + 1, len = l;
	while (i <= mid && j <= r) {
		if (a[i] <= a[j]) {
			b[len++] = a[i++];
		} else {
			b[len++] = a[j++];
			res += (mid - i + 1);
		}
	}
	while (i <= mid)
		b[len++] = a[i++];
	while (j <= r)
		res += (mid - i + 1), b[len++] = a[j++];
	for (int i = l; i <= r; i++)
		a[i] = b[i];
}

signed main() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	cdq(1, n);
	cout << res << endl;
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
int n, k, tree[N], f[N];

struct node {
	int a, b, c, cnt, ans;
} p[N], tmp[N];

bool cmp(node a, node b) {
	if (a.a != b.a)
		return a.a < b.a;
	else if (a.b != b.b)
		return a.b < b.b;
	else
		return a.c < b.c;
}

int lobit(int x) {
	return x & -x;
}

void add(int x, int c) {
	for (int i = x; i <= k; i += lobit(i)) {
		tree[i] += c;
	}
}

int query(int x) {
	int sum = 0;
	for (int i = x; i >= 1; i -= lobit(i)) {
		sum += tree[i];
	}
	return sum;
}

void cdq(int l, int r) {
	if (l >= r)
		return;
	int mid = (l + r) >> 1;
	cdq(l, mid);
	cdq(mid + 1, r);
	int i = l, j = mid + 1, len = l;
	while (i <= mid && j <= r) {
		if (p[i].b <= p[j].b)
			add(p[i].c, p[i].cnt), tmp[len++] = p[i++];
		else
			p[j].ans += query(p[j].c), tmp[len++] = p[j++];
	}
	while (i <= mid)
		add(p[i].c, p[i].cnt), tmp[len++] = p[i++];
	while (j <= r)
		p[j].ans += query(p[j].c), tmp[len++] = p[j++];
	for (int i = l; i <= mid; i++)
		add(p[i].c, -p[i].cnt);
	for (int i = l; i < len; i++)
		p[i] = tmp[i];
}

int main() {
	cin >> n >> k;
	for (int i = 1; i <= n; i++) {
		cin >> p[i].a >> p[i].b >> p[i].c;
		p[i].cnt = 1;
		p[i].ans = 0;
	}
	sort(p + 1, p + n + 1, cmp);
	int tot = 1;
	for (int i = 2; i <= n; i++) {
		if (p[i].a == p[tot].a && p[i].b == p[tot].b && p[i].c == p[tot].c) {
			p[tot].cnt++;
		} else {
			p[++tot] = p[i];
		}
	}
	cdq(1, tot);
	for (int i = 1; i <= tot; i++) {
		//p[i]重复了p[i].cnt
		//p[i].ans存的是多少个j能对i产生贡献
		f[p[i].ans + p[i].cnt - 1] += p[i].cnt;
	}
	for (int i = 0; i < n; i++) {
		cout << f[i] << "\n";
	}
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e5 + 5;
int n, k, tree[N], del[N], id[N];
int T[N];

struct node {
	int a, t, ans;
} p[N], q[N], tmp[N];

int lobit(int x) {
	return x & -x;
}

void add(int x, int c) {
	for (int i = x; i <= n; i += lobit(i))
		tree[i] += c;
}

int query(int x) {
	int sum = 0;
	for (int i = x; i >= 1; i -= lobit(i))
		sum += tree[i];
	return sum;
}

/*
i<j
ai>aj
ti>=tj
*/
void cdq(int l, int r) {
	if (l >= r)
		return;
	int mid = (l + r) >> 1;
	cdq(l, mid);
	cdq(mid + 1, r);
	int i = l, j = mid + 1, len = l;
	while (i <= mid && j <= r) {
		if (p[i].a > p[j].a)
			add(p[i].t, 1), tmp[len++] = p[i++];
		else {
			p[j].ans += query(n);
			if (p[j].t != 1)
				p[j].ans -= query(p[j].t - 1);
			tmp[len++] = p[j++];
		}
	}
	while (i <= mid)
		add(p[i].t, 1), tmp[len++] = p[i++];
	while (j <= r) {
		p[j].ans += query(n);
		if (p[j].t != 1)
			p[j].ans -= query(p[j].t - 1);
		tmp[len++] = p[j++];
	}
	for (int i = l; i <= mid; i++)
		add(p[i].t, -1);
	for (int i = l; i < len; i++)
		p[i] = tmp[i];
}

/*
i<j
ai>aj
ti>=tj
*/
void CDQ(int l, int r) {
	if (l >= r)
		return;
	int mid = (l + r) >> 1;
	CDQ(l, mid);
	CDQ(mid + 1, r);
	int i = l, j = mid + 1, len = l;
	while (i <= mid && j <= r) {
		if (q[j].a < q[i].a)
			add(q[j].t, 1), tmp[len++] = q[j++];
		else {
			q[i].ans += query(n) - query(q[i].t);
			tmp[len++] = q[i++];
		}
	}
	while (i <= mid) {
		q[i].ans += query(n);
		q[i].ans -= query(q[i].t);
		tmp[len++] = q[i++];
	}
	while (j <= r)
		add(q[j].t, 1), tmp[len++] = q[j++];
	for (int i = mid + 1; i <= r; i++)
		add(q[i].t, -1);
	for (int i = l; i < len; i++)
		q[i] = tmp[i];
}

/*
1   5   3   4   2
2   1   4   3   4
00  30  00  10  01
*/
signed main() {
	cin >> n >> k;
	for (int i = 1; i <= n; i++) {
		cin >> p[i].a;
		id[p[i].a] = i;
		p[i].t = k;
	}
	for (int i = 1; i <= k; i++) {
		cin >> del[i];
		p[id[del[i]]].t = i;
	}
	for (int i = 1; i <= n; i++)
		q[i] = p[i];
	cdq(1, n);
	memset(tree, 0, sizeof(tree));
	CDQ(1, n);
	reverse(q + 1, q + n + 1);
	int res = 0;
	for (int i = 1; i <= n; i++) {
		//	cout << p[i].a << " " << p[i].ans << " " << q[i].a << " " << q[i].ans << endl;
		res += q[i].ans + p[i].ans;
		p[i].ans = p[i].ans + q[i].ans;
		//	cout << p[i].a << " " << p[i].ans << endl;
	}
	reverse(p + 1, p + n + 1);
	for (int i = 1; i <= n; i++)
		T[i] = p[i].a;
	for (int i = 1; i <= k; i++) {
		cout << res << endl;
		int id = lower_bound(T + 1, T + n + 1, del[i]) - T;
		res -= p[id].ans;
	}
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e5 + 5;
int n, red[N], blue[N], siz[N], dfn[N], cnt, tree[N];
vector<int>e[N];

struct node {
	int a, b, dfn, ans, size, num;
} p[N], tmp[N];

void dfs1(int x, int fa) {
	siz[x] = 1;
	for (auto v : e[x]) {
		if (v == fa)
			continue;
		dfs1(v, x);
		siz[x] += siz[v];
	}
}

void dfs2(int x, int fa) {
	dfn[x] = ++cnt;
	p[cnt] = {red[x], blue[x], dfn[x], 0, siz[x], x};
	for (auto v : e[x]) {
		if (v == fa)
			continue;
		dfs2(v, x);
	}
}

bool cmp(node a, node b) {
	if (a.a != b.a)
		return a.a < b.a;
	else if (a.b != b.b)
		return a.b < b.b;
	else
		return a.dfn > b.dfn;
}

int lobit(int x) {
	return x & -x;
}

void add(int x, int c) {
	for (int i = x; i <= n; i += lobit(i))
		tree[i] += c;
}

int query(int x) {
	int sum = 0;
	for (int i = x; i >= 1; i -= lobit(i))
		sum += tree[i];
	return sum;
}

void cdq(int l, int r) {
	if (l >= r)
		return;
	int mid = (l + r) >> 1;
	cdq(l, mid);
	cdq(mid + 1, r);
	int i = l, j = mid + 1, len = l;
	while (i <= mid && j <= r) {
		if (p[i].b <= p[j].b)
			add(p[i].dfn, 1), tmp[len++] = p[i++];
		else
			p[j].ans += query(p[j].dfn + p[j].size - 1) - query(p[j].dfn), tmp[len++] = p[j++];
	}
	while (i <= mid)
		add(p[i].dfn, 1), tmp[len++] = p[i++];
	while (j <= r)
		p[j].ans += query(p[j].dfn + p[j].size - 1) - query(p[j].dfn), tmp[len++] = p[j++];
	for (int i = l; i <= mid; i++)
		add(p[i].dfn, -1);
	for (int i = l; i <= r; i++) {
		p[i] = tmp[i];
	}
}

bool cmp2(node a, node b) {
	return a.num < b.num;
}

signed main() {
	cin >> n;
	for (int i = 1; i < n; i++) {
		int x, y;
		cin >> x >> y;
		e[x].push_back(y);
		e[y].push_back(x);
	}
	for (int i = 1; i <= n; i++) {
		cin >> red[i] >> blue[i];
	}
	dfs1(1, 0);
	dfs2(1, 0);
	sort(p + 1, p + n + 1, cmp);
	cdq(1, n);
	sort(p + 1, p + n + 1, cmp2);
	for (int i = 1; i <= n; i++) {
		if (!p[i].ans)
			continue;
		cout << p[i].ans << endl;
	}
	return 0;
}