Problem: Example

Input

3
1 3 3
2
1 2
1 3


Output

5

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
#define syosu(x) fixed<<setprecision(x)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef pair<double,double> pdd;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<string> vs;
typedef vector<P> vp;
typedef vector<vp> vvp;
typedef vector<pll> vpll;
typedef pair<int,P> pip;
typedef vector<pip> vip;
const int inf=1<<30;
const ll INF=1ll<<60;
const double pi=acos(-1);
const double eps=1e-8;
const ll mod=1e9+7;
const int dx[4]={-1,0,1,0},dy[4]={0,-1,0,1};

class Union_Find_Tree{
	public:
	vi p,r,s;
	Union_Find_Tree(int n){
		p=r=vi(n);
		s=vi(n,1);
		for(int i=0;i<n;i++) p[i]=i;
	}
	int Par(int x){
		if(p[x]==x) return x;
		return p[x]=Par(p[x]);
	}
	int Size(int x){return s[Par(x)];}
	bool Unite(int x,int y){
		x=Par(x);
		y=Par(y);
		if(x==y) return 0;
		if(r[x]<r[y]){
			p[x]=y;
			s[y]+=s[x];
		}
		else{
			p[y]=x;
			s[x]+=s[y];
			if(r[x]==r[y]) r[x]++;
		}
		return 1;
	}
	bool Same(int x,int y){return Par(x)==Par(y);}
};

int n,m;
vi a,c;
vvi g,G;

void dfs(int v){
	int t=1;
	for(auto u:G[v]){
		if(!c[u]) dfs(u);
		t=max(t,c[u]+1);
	}
	c[v]=t;
}

int main(){
	cin>>n;
	a=c=vi(n);
	g=G=vvi(n);
	for(int i=0;i<n;i++) cin>>a[i];
	cin>>m;
	for(int i=0;i<m;i++){
		int u,v;
		cin>>u>>v;
		u--;v--;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	Union_Find_Tree uft(n);
	vvp b(n);
	for(int v=0;v<n;v++){
		b[v].push_back({a[v],v});
		for(auto u:g[v]) b[v].push_back({a[u],u});
		sort(b[v].begin(),b[v].end());
		for(int j=1;j<b[v].size();j++) if(b[v][j-1].first==b[v][j].first) uft.Unite(b[v][j-1].second,b[v][j].second);
	}
	for(int v=0;v<n;v++) for(int j=1;j<b[v].size();j++) if(b[v][j-1].first<b[v][j].first) G[uft.Par(b[v][j].second)].push_back(uft.Par(b[v][j-1].second));
	for(int i=0;i<n;i++) if(!c[i]) dfs(i);
	ll res=0;
	for(int i=0;i<n;i++) res+=c[uft.Par(i)];
	cout<<res<<endl;
}