Problem: Example

Input

3
1 3 3
2
1 2
1 3


Output

5

Solution (in CPP):

Solution:
#include<iostream>
#include<vector>
#include<algorithm>
#include<numeric>
#include<queue>
#include<set>
using namespace std;
typedef long long int lli;
typedef pair<int, int> pii;
class UnionFind{
public:
  UnionFind();
  UnionFind(int _n){init(_n);}
  void init(int _n){
    n = _n;
    rank.resize(n, 0);
    parent.resize(n, -1);
  }
  int find(int x){
    if(parent[x] < 0)return x;
    else return parent[x] = find(parent[x]);
  }
  void unite(int x, int y){
    x = find(x), y = find(y);
    if(x == y)return;
    if(rank[x] < rank[y]){
      parent[y] += parent[x];
      parent[x] = y;
    }else{
      parent[x] += parent[y];
      parent[y] = x;
      if(rank[x] == rank[y])rank[x]++;
    }
  }
  bool same(int x, int y){
    return find(x) == find(y);
  }
  int size(int v){
    if(parent[v] < 0)return -parent[v];
    else return size(parent[v]);
  }
private:
  int n;
  vector<int> rank, parent;
};


int main(){
  int n, m;
  std::cin >> n;
  vector<lli> salary(n, 0), c(n);;
  UnionFind uf(n);
  for (int i = 0; i < n; i++){
    std::cin >> c[i];
  }
  std::cin >> m;
  vector<vector<int> > g(n);
  vector<vector<pii> > gg(n);
  for (int i = 0; i < m; i++) {
    int to, from;
    std::cin >> to >> from;
    to--, from--;
    if(c[to] < c[from])swap(to, from);
    if(c[to] == c[from])uf.unite(to, from);
    else g[from].push_back(to);
    gg[from].push_back(pii(c[to], to));
    gg[to].push_back(pii(c[from], from));
  }
  for (int i = 0; i < n; i++) {
    sort(gg[i].begin(), gg[i].end());
    for (int j = 1; j < gg[i].size(); j++) {
      auto &prev = gg[i][j - 1], cur = gg[i][j];
      if(prev.first == cur.first)uf.unite(prev.second, cur.second);
      else g[prev.second].push_back(cur.second);
    }
  }
  vector<int> id;
  for (int i = 0; i < n; i++) {
    if(uf.find(i) == i){
      id.push_back(i);
      salary[i] = 1;
    }else{
      copy(g[i].begin(), g[i].end(), back_inserter(g[uf.find(i)]));
      g[i].clear();
    }
  }
  sort(id.begin(), id.end(), [&](int a, int b){return c[a] < c[b];});
  lli ans = 0;
  for (int i: id) {
    for (int to: g[i]) salary[uf.find(to)] = max(salary[uf.find(to)], salary[i] + 1);
    ans += 1LL * salary[i]*uf.size(i);
    }
  std::cout << ans << std::endl;
  return 0;
}