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 int long long

const int inf = 1LL<<55;

using vint = vector<int>;
using Pi = pair<int, int>;
using Graph1 = vector<vint>;
using Graph2 = vector<set<int>>;

struct UnionFind {
  vint data;
  UnionFind(int N):data(N, -1){}
  int find(int x) {
    return data[x] < 0 ? x : data[x] = find(data[x]);
  }
  int size(int x) {
    return -data[find(x)];
  }
  bool same(int x, int y) {
    return find(x) == find(y);
  }
  bool unite(int x, int y) {
    x = find(x), y = find(y);
    if(x == y) return false;
    if(data[x] < data[y]) swap(x, y);
    data[x] += data[y];
    data[y] = x;
    return true;
  }
};

#define MAX_N 100000

int N, M;
vint c;
Graph1 graph;
Graph2 dag;

int dp[MAX_N];

map<int, int> convmap(vint c) {
  map<int, int> res;
  int n = c.size();
  vector<Pi> vec;
  for(int i = 0; i < n; i++) vec.emplace_back(c[i], i);
  sort(vec.begin(), vec.end());
  for(int i = 0; i < n; i++) res[vec[i].second] = i;
  return res;
}

signed main() {
  cin >> N;
  graph.resize(N);
  c.resize(N);
  for(int i = 0; i < N; i++) cin >> c[i];
  auto mp = convmap(c);
  sort(c.begin(), c.end());
  cin >> M;
  for(int i = 0; i < M; i++) {
    int a, b;
    cin >> a >> b; --a, --b;
    a = mp[a], b = mp[b];
    graph[a].push_back(b);
    graph[b].push_back(a);
  }
  UnionFind uf(N);
  for(int i = 0; i < N; i++) {
    graph[i].push_back(i);
    sort(graph[i].begin(), graph[i].end());
    for(int j = 1; j < (int)graph[i].size(); j++) {
      int u = graph[i][j-1];
      int v = graph[i][j];
      if(c[u] == c[v]) uf.unite(u, v);
    }
  }
  dag.resize(N);
  for(int i = 0; i < N; i++) {
    for(int j = 1; j < (int)graph[i].size(); j++) {
      int u = graph[i][j-1];
      int v = graph[i][j];
      if(!uf.same(u, v)) dag[uf.find(u)].insert(v);
    }
  }
  vint in(N), ord;
  for(int u = 0; u < N; u++) {
    for(int v : dag[u]) in[uf.find(v)]++;
  }
  queue<int> que;
  for(int u = 0; u < N; u++) {
    if(u == uf.find(u) && in[u] == 0) que.push(u);
  }
  while(!que.empty()) {
    int u = que.front(); que.pop();
    ord.push_back(uf.find(u));
    for(int v : dag[uf.find(u)]) {
      in[uf.find(v)]--;
      if(in[uf.find(v)] == 0) que.push(uf.find(v));
    }
  }
  for(int i = 0; i < N; i++) dp[i] = 1;
  for(int u : ord) {
    for(int v : dag[uf.find(u)]) dp[uf.find(v)] = max(dp[uf.find(v)], dp[uf.find(u)]+1);
  }
  int ans = 0;
  for(int i = 0; i < N; i++) {
    if(i != uf.find(i)) continue;
    ans += dp[i]*uf.size(i);
  }
  cout << ans << endl;

  return 0;
}