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 <utility>
#include <set>
#include <map>
using namespace std;
typedef long long int lli;

struct UnionFindTree{
    vector<int> v;
    vector<int> rank;
    
    UnionFindTree(int n): v(n, -1), rank(n, 0){}
    int Find(int x){
        if(v[x] < 0) return x;
        return v[x] = Find(v[x]);
    }
    void Union(int a, int b){
        a = Find(a);
        b = Find(b);
        if(a == b) return;
        if(rank[a] < rank[b]) swap(a, b);
        if(rank[a] == rank[b]) rank[a]++;
        v[b] = a;
    }
};

lli solve(vector<int> &c, vector<vector<int> > &adj){
	int n = c.size();
	//unite nodes that must be equal
	UnionFindTree uft(n);
	for(int i=0; i<n; i++){
		map<int, vector<int> > ctoi;
		for(int j: adj[i]){
			ctoi[c[j]].push_back(j);
		}
		for(auto itr: ctoi){
			vector<int> &a = itr.second;
			for(int j=0; j<(int)a.size()-1; j++){
				if(c[a[j]] == c[a[j+1]]) uft.Union(a[j], a[j+1]);
			}
		}
	}
	
	map<int, set<int> > tmp;
	for(int i=0; i<n; i++){
		tmp[uft.Find(i)].insert(i);
	}
	map<int, set<int> > eq;//
	for(auto itr : tmp){
		set<int> &a = itr.second;
		if((int)a.size() <= 1) continue;
		eq[*max_element(a.begin(), a.end())] = a;
	}
	vector<pair<int, int> > con(n);//
	for(int i=0; i<n; i++){
		con[i] = make_pair(c[i], i);
	}
	sort(con.begin(), con.end());
	
	//calc saraly
	vector<int> salary(n);
	vector<int> slast(n, 0), clast(n, 0);
	for(int i=0; i<n; i++){
		int node = con[i].second;
		int s = 1;
		for(int j: adj[node]){
			if(clast[j] < c[node]){
				s = max(s, slast[j] +1);
			}else{
				s = max(s, slast[j]);
			}
		}
		for(int j: adj[node]){
			slast[j] = s;
			clast[j] = c[node];
		}
		salary[node] = s;
		
		//propagation
		if(eq.count(node) != 0){
			int s = 1;
			for(int j: eq[node]){
				s = max(s, salary[j]);
			}
			for(int j: eq[node]){
				salary[j] = s;
				for(int k: adj[j]){
					slast[k] = s;
				}
			}
		}
	}
	
	lli ret = 0;
	for(int i=0; i<n; i++){
		ret += salary[i];
	}
	return ret;
}

int main(){
	int n;
	cin >> n;
	vector<int> c(n);
	for(int i=0; i<n; i++){
		cin >> c[i];
	}
	
	int m;
	cin >> m;
	vector<vector<int> > adj(n);
	for(int i=0; i<m; i++){
		int a,b;
		cin >> a >> b;
		a--; b--;
		adj[a].push_back(b);
		adj[b].push_back(a);
	}
	for(int i=0; i<n; i++){
		adj[i].push_back(i);
	}
	
	cout << solve(c, adj) << endl;
	return 0;
}