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;
 
 
struct edge{
  int to,cost;
  bool operator < ( const edge &p)const{
    return (cost == p.cost? to < p.to :cost < p.cost);
  }
};
struct state{
  int pos,cost;
  bool operator < (const state &p)const{
    return cost > p.cost;
  }
};
 
typedef long long ll;
 
#define MAX 100005
int pa[MAX],ra[MAX];
int t[MAX],h[MAX],d[MAX];
 
vector<edge> G[MAX];
vector<edge> g[MAX];
int n,m;
 
void init();
int find(int x);
void unite(int x,int y);
ll solve();
 
int main(){
  while( scanf("%d",&n)!=EOF){
    init();
    for(int i=1;i<=n;i++)scanf("%d",&h[i]);
    scanf("%d",&m);
    int a,b;
    for(int i=1;i<=m;i++){
      scanf("%d %d",&a,&b);
      g[a].push_back((edge){b,h[b]});
      g[b].push_back((edge){a,h[a]});
      if(h[a]<h[b]){        
        G[a].push_back((edge){b,h[b]});
      }else if(h[a]>h[b]){
        G[b].push_back((edge){a,h[a]});
      }else{        
        unite(a,b);
      }
    }
 
 
    for(int i=1;i<=n;i++){
      sort(g[i].begin(),g[i].end());
      for(int j=1;j<(int)g[i].size();j++){
        if(g[i][j-1].cost==g[i][j].cost){
          unite(g[i][j-1].to,g[i][j].to);
        }else if(g[i][j-1].cost<g[i][j].cost){
          G[ g[i][j-1].to ].push_back( g[i][j] );
        }
      }
    }
 
  
    for(int i=1;i<=n;i++){
      int id=find(i);
      t[id]++;
      if(i==id)continue;
      for(int j=0;j<(int)G[i].size();j++){
        edge e=G[i][j];
        G[id].push_back(e);
      }
    }
  
    cout<<solve()<<endl;
 
    break;
  }
  return 0;
}
 
ll solve(){
  priority_queue< state > Q;
 
  for(int i=1;i<=n;i++){
    if(i==find(i))Q.push((state){i,h[i]});
  }
  
  while(!Q.empty()){
    state s=Q.top();Q.pop();
    int pos=s.pos;
    int cost=d[s.pos];
    for(int i=0;i<(int)G[pos].size();i++){
      edge e=G[pos][i];
      e.to=find(e.to);
      d[e.to]=max(d[e.to],cost+1);      
    }
  }
  ll ans=0;
  for(int i=1;i<=n;i++)ans+= (ll)d[i] * (ll)t[i];  
  return ans;
}
 
void init(){
  for(int i=0;i<MAX;i++){
    pa[i]=i;
    ra[i]=0;
    t[i]=0;
    d[i]=1;
    G[i].clear();
    g[i].clear();
  }  
}
 
 
 
int find(int x){
  if(pa[x]==x)return x;
  else return pa[x]=find(pa[x]);
}
 
void unite(int x,int y){
  x=find(x);
  y=find(y);
  if(x==y)return;
  if(ra[x]<ra[y])pa[x]=y;
  else {
    pa[y]=x;
    if(ra[x]==ra[y])ra[x]++;
  }  
}