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 r(i,n) for(int i=0;i<n;i++)
#define int long long
typedef pair<int,int>P;

struct UnionFind{
  int n;
  vector<int> ran,p,cnt;
  UnionFind(){}
  UnionFind(int sz):n(sz),ran(sz,1),p(sz,0){
    r(i,sz)p[i]=i;
  }
  int find(int x){
    return (x==p[x]?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(ran[x]<ran[y]) swap(x,y);
    ran[x]+=ran[y];
    p[y]=x;
  }
  int sum(int x){
    return ran[find(x)];
  }
};

int n,m,w[100009];
vector<vector<int> >v(100009),G(100009),uni(100009);
vector<P>T;
int dp[100009],ans;
bool used[100009];
UnionFind U(100009);

void add(int a,int b){ U.unite(a,b);}

signed main(){
  cin>>n;
  //r(i,n)dp[i]=1;
  r(i,n)cin>>w[i];
  cin>>m;
  r(i,m){
    int x,y;
    cin>>x>>y;
    x--;y--;
    v[x].push_back(y);
    v[y].push_back(x);
  }
  r(i,n){
    vector<P>a;
    r(j,v[i].size()){
      a.push_back(P(w[v[i][j]],v[i][j]));
      if(w[i]<=w[v[i][j]]){
        G[i].push_back(v[i][j]);
        if(w[i]==w[v[i][j]])add(i,v[i][j]);
      }
    }
    sort(a.begin(),a.end());
    r(j,(int)a.size()-1){
      G[a[j].second].push_back(a[j+1].second);
      if(a[j].first==a[j+1].first){
        add(a[j].second,a[j+1].second);
      }
    }
  }
  r(i,n){
    T.push_back(P(w[i],i));
    uni[U.find(i)].push_back(i);
  }
  r(i,n){
    sort(G[i].begin(),G[i].end());
    G[i].erase(unique(G[i].begin(),G[i].end()),G[i].end());
  }
  sort(T.begin(),T.end());
  r(i,n)if(U.find(T[i].second)==T[i].second){
    int x=T[i].second;
    int y=T[i].first;
    int cnt=1,MAX=0;
    r(k,uni[x].size()){
      MAX=max(MAX,dp[uni[x][k]]);
    }
    r(k,uni[x].size()){
      int X=uni[x][k];
      r(j,G[X].size()){
        int nxt=G[X][j];
        dp[nxt]=max(dp[nxt],MAX+1);
      }
    }
    ans+=U.sum(x)*(MAX+1);
  }
  cout<<ans<<endl;
}