Problem: Example

Input

3
1 3 3
2
1 2
1 3


Output

5

Solution (in CPP):

Solution:
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define all(a) (a).begin(),(a).end()
using namespace std;
typedef vector<int> vi;
typedef pair<int,int> pii;
 
class UnionFind{
  vi p,r;
public:
  UnionFind(int n):p(n,-1),r(n,0){}
  int find(int x){ return (p[x]<0)?x:(p[x]=find(p[x])); }
  bool same(int x,int y){return find(x)==find(y);}
  void unite(int x,int y){
    x = find(x); y = find(y);
    if(x==y)return;
 
    if(r[x]<r[y])p[x] = y;
    else p[y] = x;
    if(r[x] == r[y])r[x]++;
  }
};
 
int main(){
  cin.tie(0); ios::sync_with_stdio(0);
 
  int n;
  cin >> n;
  vi c(n);
  rep(i,n)cin >> c[i];
  vector< vector<pii> > nei(n);
  UnionFind uf(n);
  vector< vi > g(n);
 
  int m;
  cin >> m;
  rep(i,m){
    int a,b;
    cin >> a >> b; a--; b--;
    if(c[a] == c[b])uf.unite(a,b);
    else if(c[a] < c[b])g[a].push_back(b);
    else g[b].push_back(a);
    nei[a].push_back(pii(c[b],b));
    nei[b].push_back(pii(c[a],a));
  }
 
  rep(i,n){
    if(nei[i].empty())continue;
 
    sort(all(nei[i]));
    rep(j,nei[i].size()-1){
      pii u = nei[i][j], v = nei[i][j+1];
      if(u.first == v.first){
	uf.unite(u.second,v.second);
      }else{
	g[u.second].push_back(v.second);
      }
    }
  }
 
  vi comp_size(n,1);
  rep(i,n){
    rep(j,g[i].size())g[i][j] = uf.find(g[i][j]);
  }
 
  rep(i,n){
    int u = uf.find(i);
    if(u != i){
      comp_size[u]++; comp_size[i]--;
      rep(j,g[i].size())g[u].push_back(g[i][j]);
      g[i].clear();
    }
  }
 
  vi deg(n,0), ord;
  queue<int> q;
  rep(i,n){
    if(i == uf.find(i)){
      sort(all(g[i]));
      g[i].erase(unique(all(g[i])), g[i].end());
      for(int v : g[i])deg[v]++;
    }else deg[i] = -1;
  }
 
  rep(i,n){
    if(deg[i] == 0)q.push(i);
  }
 
  while(q.size()){
    int v = q.front(); q.pop();
    ord.push_back(v);
    for(int u : g[v]){
      deg[u]--;
      if(deg[u]==0)q.push(u);
    }
  }
 
  vi dp(n,1);
  long long res = 0;
  for(int v : ord){
    res += (long long)dp[v] * comp_size[v];
    for(int u : g[v]){
      dp[u] = max(dp[u], dp[v]+1);
    }
  }
 
  cout << res << endl;
}