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;

using Graph=vector<vector<int>>;
int main(){
    int n;
    cin>>n;
    vector<int> c(n);
    for(int i=0;i<n;i++) cin>>c[i];
    int m;
    cin>>m;

    Graph inputG(n);
    for(int i=0;i<m;i++){
        int a,b;
        cin>>a>>b;
        a--,b--;
        inputG[a].push_back(b);
        inputG[b].push_back(a);
    }
    
    Graph g(n);
    {
        vector<set<int>> tmpG(n);
        for(int i=0;i<n;i++){
            sort(inputG[i].begin(),inputG[i].end(),[&](int lhs,int rhs){return c[lhs]>c[rhs];});
            for(int j=0;j<inputG[i].size();j++){
                if(c[i]>=c[inputG[i][j]]) tmpG[i].insert(inputG[i][j]);
                if(j+1<inputG[i].size()){
                    tmpG[inputG[i][j]].insert(inputG[i][j+1]);
                    if(c[inputG[i][j]]==c[inputG[i][j+1]]) tmpG[inputG[i][j+1]].insert(inputG[i][j]);
                }
            }
        }
        for(int i=0;i<n;i++) g[i]=vector<int>(tmpG[i].begin(),tmpG[i].end());
    }
    
    vector<int> idx(n);
    iota(idx.begin(),idx.end(),0);
    sort(idx.begin(),idx.end(),[&](int lhs,int rhs){return c[lhs]<c[rhs];});
    vector<int> p(n);
    for(auto id:idx){
        vector<int> vs;
        function<void(int)> dfs=[&](int v){
            if(p[v]!=0) return;
            p[v]=-1;
            vs.push_back(v);
            for(auto to:g[v]){
                if(c[to]==c[v]) dfs(to);
            }
        };
        dfs(id);
        int x=1;
        for(auto v:vs){
            for(auto to:g[v]){
                x=max(x,p[to]+1);
            }
        }
        for(auto v:vs) p[v]=x;
    }
    cout<<accumulate(p.begin(),p.end(),0LL)<<endl;
    return 0;
}