Problem: Example

Input

3
1 3 3
2
1 2
1 3


Output

5

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
#define MAX_N 100010
#define N MAX_N
#define rank Asdfiasofsad
#define int long long
using namespace std;

class UF{
public:
  vector<int> par,rank;
  UF(){
    par.resize(MAX_N),rank.resize(MAX_N);
    for(int i=0;i<MAX_N;i++)par[i]=i,rank[i]=0;
  }

  UF(int n){
    par.resize(n),rank.resize(n);
    for(int i=0;i<n;i++)par[i]=i,rank[i]=0;
  }

  int find(int x){
    if(par[x]==x)return x;
    return par[x]=find(par[x]);
  }
  
  void unite(int x,int y){
    x=find(x), y=find(y);
    if(x==y)return;
    if(rank[x]<rank[y])par[x]=y;
    else{
      par[y]=x;
      if(rank[x]==rank[y])rank[x]++;
    }
  }

  bool same(int x,int y){return find(x)==find(y);}
};

vector<int> G[N];
map<int,int>M[N];
vector<int> grp[N];

typedef pair<int,int> P;
signed main(){
  int n,m;
  cin>>n;
  P C[N];

  for(int i=0,a;i<n;i++)cin>>a,C[i]=P(a,i);

  cin>>m; 
  for(int i=0;i<m;i++){
    int a,b;
    cin>>a>>b;a--,b--;
    G[a].push_back(b);
    G[b].push_back(a);
  }

  UF A; 
  for(int i=0;i<n;i++) M[i][C[i].first] = i;

  for(int i=0;i<n;i++)
    for(int p:G[i])
      if(M[p].count(C[i].first)) A.unite(i,M[p][C[i].first]);
      else M[p][C[i].first] = i;

  for(int i=0;i<n;i++)grp[A.find(i)].push_back(i);

  sort(C,C+n);
  int money[N]={};
  int ans = 0;
  for(int i=0;i<n;i++){
    int c = C[i].first;
    int p = C[i].second;
    if(A.find(p) != p) continue;

    int mx = 0;
    for(int pos:grp[p]){
      mx = max(mx,money[pos]);
      for(int nx:G[pos]) mx = max(mx,money[nx]);
    }
    mx++;
    ans += mx*grp[p].size();
    for(int pos:grp[p]){
      money[pos] = mx;
      for(int nx:G[pos]) money[nx] = mx;
    }
  }
  cout<<ans<<endl;


  return 0;
}