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 UnionFind
{
  vector< int > data;

  UnionFind(int sz) : data(sz, -1) {}

  int find(int k)
  {
    if(data[k] < 0) return (k);
    return (data[k] = find(data[k]));
  }

  void unite(int x, int y)
  {
    x = find(x);
    y = find(y);
    if(x == y) return;
    if(data[x] > data[y]) swap(x, y);
    data[x] += data[y];
    data[y] = x;
  }

  int size(int k)
  {
    return (-data[find(k)]);
  }
};


int main()
{
  int N, C[100000], M;
  vector< int > g[100000];
  vector< pair< int, int > > beet[100000];
  int dp[100000];

  scanf("%d", &N);
  for(int i = 0; i < N; i++) {
    scanf("%d", &C[i]);
  }
  scanf("%d", &M);

  UnionFind tree(N);
  for(int i = 0; i < M; i++) {
    int a, b;
    scanf("%d %d", &a, &b);
    --a, --b;
    if(C[a] > C[b]) swap(a, b);
    if(C[a] == C[b]) tree.unite(a, b);
    else g[a].push_back(b);
    beet[a].emplace_back(C[b], b);
    beet[b].emplace_back(C[a], a);
  }

  for(int i = 0; i < N; i++) {
    sort(begin(beet[i]), end(beet[i]));
    for(int j = 1; j < beet[i].size(); j++) {
      auto &pv = beet[i][j - 1], cr = beet[i][j];
      if(pv.first == cr.first) tree.unite(pv.second, cr.second);
      else g[pv.second].push_back(cr.second);
    }
  }

  vector< int > order;
  for(int i = 0; i < N; i++) {
    if(tree.find(i) == i) {
      order.push_back(i);
      dp[i] = 1;
    } else {
      for(int j : g[i]) g[tree.find(i)].push_back(j);
      copy(begin(g[i]), end(g[i]), back_inserter(g[tree.find(i)]));
      g[i].clear();
    }
  }

  sort(begin(order), end(order), [&](int a, int b)
  {
    return (C[a] < C[b]);
  });

  long long ret = 0;
  for(int idx : order) {
    for(int to : g[idx]) dp[tree.find(to)] = max(dp[tree.find(to)], dp[idx] + 1);
    ret += 1LL * dp[idx] * tree.size(idx);
  }

  printf("%lld\n", ret);
}