Problem: Example

Input

3
1 3 3
2
1 2
1 3


Output

5

Solution (in CPP):

Solution:
#include<iostream>
#include<string>
#include<cstdio>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<ciso646>
#include<random>
#include<map>
#include<set>
#include<complex>
#include<bitset>
#include<stack>
#include<unordered_map>
#include<utility>
using namespace std;
typedef long long ll;
typedef unsigned long long ul;
typedef unsigned int ui;
const ll mod = 1000000007;
typedef double ld;
typedef complex<ld> Point;
const ll INF = mod * mod;
typedef pair<int, int> P;
#define stop char nyaa;cin>>nyaa;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
const ld eps = 1e-8;
const ld pi = acos(-1.0);
typedef pair<ld, ld> LDP;
typedef pair<ll, ll> LP;

struct uf {
private:
	vector<int> par, ran;
public:
	void init(int n) {
		par.resize(n, 0);
		ran.resize(n, 0);
		rep(i, n) {
			par[i] = i;
		}
	}
	int find(int x) {
		if (par[x] == x)return x;
		else return par[x] = find(par[x]);
	}
	void unite(int x, int y) {
		x = find(x), y = find(y);
		if (x == y)return;
		if (ran[x] < ran[y]) {
			par[x] = y;
		}
		else {
			par[y] = x;
			if (ran[x] == ran[y])ran[x]++;
		}
	}
	bool same(int x, int y) {
		return find(x) == find(y);
	}
};

vector<int> G[1 << 18];
int c[1 << 18];
int ma[1 << 18];

int col[1 << 18];

vector<P> g[1 << 18];
bool used[1 << 18];
void solve() {
	int n; cin >> n;
	rep(i, n) {
		cin >> c[i];
	}
	int m; cin >> m;
	vector<P> v;
	rep(i, m) {
		int a, b; cin >> a >> b; a--; b--;
		g[a].push_back({ c[b],b }); g[b].push_back({ c[a],a });
	}
	uf u; u.init(n);
	rep(i, n) {
		sort(g[i].begin(), g[i].end());
		rep(j, g[i].size()) {
			int le = j;
			while (j + 1 < g[i].size() && g[i][j].first == g[i][j+1].first) {
				j++;
				u.unite(g[i][j].second, g[i][le].second);
			}

		}
	}
	rep(i, n) {
		rep(j, g[i].size()) {
			int to = g[i][j].second;
			if (c[i] == c[to])u.unite(i, to);
		}
	}
	rep(i, n) {
		int p = u.find(i);
		rep(j, g[i].size()) {
			int to = g[i][j].second;
			to = u.find(to);
			G[p].push_back(to);
		}
	}
	//cout << m << endl;
	rep(i, n) {
		//int p = u.find(i);
		//if (used[p])continue;
		//used[p] = true;
		//v.push_back({ c[p],p });
		v.push_back({ c[i],i });
	}
	sort(v.begin(), v.end());
	rep(i, v.size()) {
		int le = i;
		while (i + 1 < v.size()&&v[i].first == v[i + 1].first)i++;
		//vector<int> memo;
		for (int j = le; j <= i; j++) {
			int id = v[j].second;
			int nex= 0;
			rep(k, g[id].size()) {
				int to = g[id][k].second;
				nex = max(nex, ma[to]);
				if (c[to] < c[id]) {
					nex = max(nex, col[to]);
				}
				//nex = max({ nex, col[to],ma[to]});
			}
			int p = u.find(id);
			col[p] = max(col[p], nex + 1);
			//memo.push_back(nex + 1);
		}
		for (int j = le; j <= i; j++) {
			int id = v[j].second;
			int p = u.find(id);
			col[id] = col[p];
			rep(k, g[id].size()) {
				int to = g[id][k].second;
				ma[to] = max(ma[to], col[id]);
			}
		}
	}
	ll ans = 0;
	rep(i, n) {
		int p = u.find(i);
		ans += col[p];
		//cout << col[i] << endl;
	}
	cout << ans << endl;
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	solve();
	//stop
	return 0;
}