Problem: Example

Input

3
1 3 3
2
1 2
1 3


Output

5

Solution (in CPP):

Solution:
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define MAX 114514
int n,m;
set<int> G[MAX];
int c[MAX],d[MAX],e[MAX];
typedef pair<int,int> P;
signed main(){
  fill_n(c,MAX,0);
  fill_n(d,MAX,0);
  fill_n(e,MAX,-1);
  cin>>n;
  for(int i=0;i<n;i++) cin>>c[i];
  cin>>m;
  for(int i=0;i<m;i++){
    int a,b;
    cin>>a>>b;
    a--;b--;
    G[a].insert(b);
    G[b].insert(a);
  }
  priority_queue<P,vector<P>,greater<P> > q;
  for(int i=0;i<n;i++) q.push(P(c[i],i));
  while(!q.empty()){
    int x=q.top().first;
    //cout<<x<<endl;
    set<int> v;
    while(!q.empty()&&q.top().first==x){
      v.insert(q.top().second);
      q.pop();
    }
    priority_queue<P> q2;
    while(1){
      bool f=0;
      for(int w:v){
	int t=d[w];
	for(int u:G[w]) t=max(t,d[u]);
	if(e[w]<=t) q2.push(P(t,w));
      }
      while(!q2.empty()){
	P p=q2.top();q2.pop();
	int t=p.first,w=p.second;
	t=max(t,d[w]);
	for(int u:G[w]) t=max(t,d[u]);
	if(e[w]>t) continue;
	e[w]=t+1;
	f=1;
	for(int u:G[w])
	  d[u]=max(d[u],t);
      }
      if(!f) break;
    }
    for(int w:v)
      for(int u:G[w]){
	if(c[u]==c[w]&&e[u]>0){
	  if(e[u]!=e[w]) cout<<u<<" "<<w<<":"<<e[u]<<" "<<e[w]<<endl;
	  assert(e[u]==e[w]);
	}
      }
    for(int w:v)
      for(int u:G[w])
	d[u]=max(d[u],e[w]);
  }
  int ans=0;
  //for(int i=0;i<n;i++) assert(e[i]);
  //for(int i=0;i<n;i++) cout<<i<<":"<<e[i]<<endl;
  for(int i=0;i<n;i++) ans+=e[i];
  cout<<ans<<endl;
  return 0;
}

      /*
      for(int u:G[w]){
	if(c[u]==c[w]&&e[u]>0){
	  if(e[u]!=e[w]) cout<<u<<" "<<w<<":"<<e[u]<<" "<<e[w]<<" "<<b<<endl;
	  assert(e[u]==e[w]);
	}
      }
      */