Problem: Example

Input

3
1 3 3
2
1 2
1 3


Output

5

Solution (in CPP):

Solution:
#include <iostream>
#include <algorithm>
#include <numeric>
#include <vector>

using Graph = std::vector<std::vector<int>>;

struct UnionFind {
    std::vector<int> par, sz;
    int gnum;

    explicit UnionFind(int n)
        : par(n), sz(n, 1), gnum(n) {
        std::iota(par.begin(), par.end(), 0);
    }

    int find(int v) {
        return (par[v] == v) ? v : (par[v] = find(par[v]));
    }

    void unite(int u, int v) {
        u = find(u), v = find(v);
        if (u == v) return;

        if (sz[u] < sz[v]) std::swap(u, v);
        sz[u] += sz[v];
        par[v] = u;
        --gnum;
    }

    bool same(int u, int v) { return find(u) == find(v); }
    bool ispar(int v) { return v == find(v); }
    int size(int v) { return sz[find(v)]; }
};

using lint = long long;

constexpr int C = 100000;

void solve() {
    int n;
    std::cin >> n;

    std::vector<std::vector<int>> vss(C);
    std::vector<int> cs(n);
    for (int v = 0; v < n; ++v) {
        auto& c = cs[v];
        std::cin >> c;
        vss[--c].push_back(v);
    }

    Graph graph(n);

    int m;
    std::cin >> m;
    while (m--) {
        int u, v;
        std::cin >> u >> v;
        --u, --v;

        graph[u].push_back(v);
        graph[v].push_back(u);
    }

    UnionFind uf(n);
    for (int u = 0; u < n; ++u) {
        auto& es = graph[u];
        std::sort(es.begin(), es.end(),
                  [&](int v, int w) { return cs[v] < cs[w]; });

        for (auto v : es) {
            if (cs[v] == cs[u]) uf.unite(u, v);
        }

        for (int i = 0; i + 1 < (int)es.size(); ++i) {
            int v = es[i], w = es[i + 1];
            if (cs[v] == cs[w]) uf.unite(v, w);
        }
    }

    std::vector<lint> maxs(n, -1), gmax(n, -1), ans(n, 1);
    for (const auto& vs : vss) {
        for (auto v : vs) {
            for (auto u : graph[v]) {
                ans[v] = std::max(ans[v], maxs[u] + 1);
            }
            int gv = uf.find(v);
            gmax[gv] = std::max(gmax[gv], ans[v]);
        }

        for (auto v : vs) {
            ans[v] = std::max(ans[v], gmax[uf.find(v)]);
            maxs[v] = std::max(maxs[v], ans[v]);
            for (auto u : graph[v]) {
                maxs[u] = std::max(maxs[u], ans[v]);
            }
        }
    }

    std::cout << std::accumulate(ans.begin(), ans.end(), 0LL)
              << std::endl;
}

int main() {
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    std::ios::sync_with_stdio(false);

    solve();

    return 0;
}