Problem: Example

Input

3
1 3 3
2
1 2
1 3


Output

5

Solution (in CPP):

Solution:
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
#include<vector>
struct UF{
	int n;
	vector<int>parent,rank;
	UF(int n_=0):n(n_),parent(n_),rank(n_,1)
	{
		for(int i=0;i<n_;i++)parent[i]=i;
	}
	int find(int a){return parent[a]!=a?parent[a]=find(parent[a]):a;}
	bool same(int a,int b){return find(a)==find(b);}
	bool unite(int a,int b)
	{
		a=find(a),b=find(b);
		if(a==b)return false;
		if(rank[a]<rank[b])
		{
			parent[a]=b;
			rank[b]+=rank[a];
		}
		else
		{
			parent[b]=a;
			rank[a]+=rank[b];
		}
		return true;
	}
	int size(int a){return rank[find(a)];}
};
int N,M;
vector<int>G[1<<17];
int c[1<<17];
pair<int,int>check[1<<17];
int d[1<<17];
pair<int,int>parent[1<<17];
int main()
{
	cin>>N;
	vector<pair<int,int> >ids(N);
	for(int i=0;i<N;i++)
	{
		cin>>c[i];
		ids[i]=make_pair(c[i],i);
		d[i]=-1;
	}
	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);
	}
	sort(ids.begin(),ids.end());
	long ans=0;
	UF uf(N);
	for(int i=0;i<N;)
	{
		int j=i;
		while(i<N&&ids[i].first==ids[j].first)i++;
		for(int k=j;k<i;k++)
		{
			int id=ids[k].second;
			if(d[id]>=j)
			{
				uf.unite(id,ids[d[id]].second);
			}
			d[id]=k;
			for(int v:G[id])
			{
				if(d[v]>=j)
				{
					uf.unite(id,ids[d[v]].second);
				}
				d[v]=k;
			}
		}
		for(int k=j;k<i;k++)
		{
			int id=ids[k].second;
			pair<int,int>pmin=check[id];
			for(int v:G[id])pmin=max(pmin,check[v]);
			int now=pmin.first+1;
			pair<int,int>dis=make_pair(now,c[id]);
			parent[uf.find(id)]=max(parent[uf.find(id)],dis);
		}
		for(int k=j;k<i;k++)
		{
			int id=ids[k].second;
			pair<int,int>dis=parent[uf.find(id)];
			int now=dis.first;
			ans+=now;
			check[id]=max(check[id],dis);
			for(int v:G[id])check[v]=max(check[v],dis);
		}
	}
	cout<<ans<<endl;
}