Reinterpretation

Let \(S_k\) be the set of intervals where all integers between \(0\) and \(k\) occur at least once. Obviously, \(S_{k} = \emptyset\) for \(k \geq N\).

Then, \(\mathrm{mex}(\{A_l, \cdots, A_r\}) = \sum_{k=0}^{N-1} \mathrm{haveall}_k([l,r])\), where \(\mathrm{haveall}_k([l,r]) := \begin{cases} 1 & ([l,r] \in S_k) \\ 0 & ([l,r] \notin S_k). \end{cases}\)

Therefore, the answer can be represented as \(\sum_{[l,r]} \sum_{k=0}^{N-1} \mathrm{haveall}_k([l,r]) = \sum_{k=0}^{N-1} \sum_{[l,r]} \mathrm{haveall}_k([l,r]) = \sum_{k=0}^{N-1} |S_k|\), so it is sufficient to find the size of \(S_k\) for \(k = 0,\dots,N-1\).

Finding the size of \(S_k\)

For \(l=1,\dots,N\), let \(\mathrm{next}_m[l] := \min_{r \geq l} \left\{\ r\ \middle|\ A_r = m\ \right\} \cup \{N+1\}\). Also, let \(\mathrm{maxnext}_k[l] := \max_{0 \leq m \leq k} \mathrm{next}_m[l]\).

Then \([l,r] \in S_k\) if and only if \(\mathrm{maxnext}_k[l] \leq r \leq N\), and the number of such intervals \([l,r]\) is \(\sum_{1 \leq l \leq N} \left(N+1 - \mathrm{maxnext}_k[l]\right) = (N+1)^2 - \sum_{1 \leq l \leq N} \mathrm{maxnext}_k[l]\).

Hence, it suffices to, for each \(k = 0, \dots, N-1\) in ascending order, find \(\mathrm{maxnext}_k[l]\) (\(1 \leq l \leq N\)) based on \(\mathrm{maxnext}_{k-1}[l]\) (\(1 \leq l \leq N\)), and find their sum.

Finding \(\mathrm{maxnext}_k[l]\) from \(\mathrm{maxnext}_{k-1}[l]\)

We have \(\mathrm{maxnext}_k[l] = \max\left(\mathrm{maxnext}_{k-1}[l],\ \mathrm{next}_k[l]\right)\).

Let \(x_1, \dots, x_{c}\) be the indices \(x\) with \(A_x = k\) enumerated in ascending order, and put a sentinel \(x_0 := 0,\ x_{c+1} := N+1\). Then for \(1 \leq i \leq c+1\), we have \(\mathrm{next}_{k}[x_{i-1} + 1] = \dots = \mathrm{next}_{k}[x_i] = x_{i}\).

Hence, it suffices to process each of the following queries \(O(N)\) time:

• Segment chmax on \(\mathrm{maxnext}\)
• Find the sum of \(\mathrm{maxnext}\)

For any \(k\), by the time the corresponding segment-chmax queries are processed, \(\mathrm{maxnext}\) becomes weakly monotonically increasing. Therefore, a chmax query on \([x_{i-1}+1,\ x_i]\) can be written as follows:

• In a segment \([x_{i-1}+1,\ x_i]\) whose elements are weakly monotonically increasing, find the smallest \(r\) with \(\mathrm{maxnext}[r] \geq x_i\).
• Set all values of the elements in the segment \(\left[x_{i-1}+1,\ r\right)\) to \(x_i\).

Therefore, it suffices to support binary search, segment-wise assignment, and total sum retrieval, all of which can be achieved with an ordinary lazy segment tree. Alternatively, one can use the property of the segments given in the queries to process them in a balanced binary tree whose search capability is equivalent to std::map.

In any approach, the time complexity is \(O(N \log N)\).

Sample code (C++)

#include <iostream>
using std::cin;
using std::cout;
using std::cerr;
using std::endl;
#include <vector>
using std::vector;
using std::pair;
#include <map>
using std::map;
using std::max;
using std::min;


#ifdef DEBUG
const int debug = 1;
#else
const int debug = 0;
#endif

using ll = int64_t;
using P = pair<ll, ll>;

const ll FOD = 998244353;

ll n;
vector<ll> a;

void output (const ll x) {
	cout << x << "\n";
}

void solve() {
	vector<vector<ll> > idxs(n+1);
	for (ll i = 0; i < n; i++) {
		idxs[a[i]].push_back(i);
	}

	const auto cellsum = [](const P p, const ll val) -> ll {
		return (p.second - p.first) * val;
	};
	map<P, ll> slopes;
	ll sum = 0;
	for (ll i = 0; i <= n; i++) {
		slopes.insert({{i, i+1}, i});
		sum += cellsum({i, i+1}, i);
	}

	const auto split = [&](const ll x) -> bool {
		// find the largest key[l, r) s.t. l <= x
		auto it = slopes.lower_bound({x+1, -1}); // smallest s.t. l > x
		if (it == slopes.begin()) return false;
		--it; // largest s.t. l <= x

		const P p = it->first;
		const ll val = it->second;
		if (x <= p.first || p.second <= x) return false;

		// split p into two (doesn't affect sum)
		slopes.erase(it);
		slopes.insert({{p.first, x}, val});
		slopes.insert({{x, p.second}, val});
		return true;
	};

	ll ans = 0;
	for (ll xi = 0; xi <= n-1; xi++) {
		vector<ll> ris = idxs[xi];
		ris.push_back(n);

		for (ll i = 0; i < ris.size(); i++) {
			ll l = ((i == 0) ? 0 : (ris[i-1] + 1));
			ll r = ris[i] + 1;
			ll x = ris[i];
			// [l, r) <-chmax(x)

			split(l);
			split(r);

			// erase slopes with key within [l, r) and value of <x
			ll delr = l; // r-value of whole deleted interval [l. delr)
			while (true) {
				auto it = slopes.lower_bound({l, -1}); // smallest L >= l
				if (it == slopes.end()) break;
				const P p = it->first;
				const ll val = it->second;

				if (val >= x) break; // value of <x ?
				if (p.first >= r) break; // within [l, r) ?

				slopes.erase(it);
				sum -= cellsum(p, val);
				delr = p.second;
			}

			if (l < delr) {
				slopes.insert({{l, delr}, x});
				sum += cellsum({l, delr}, x);
			}
		}


		// count intervals that contain 0, ..., xi
		// which is sum of n - s[i]
		// which is n(n+1) - sum
		ans += n*(n+1) - sum;
	}

	output(ans);
	return;
}

int main (void) {
	std::cin.tie(nullptr);
	std::ios_base::sync_with_stdio(false);

	cin >> n;
	a.resize(n);
	for (ll i = 0; i < n; i++) {
		cin >> a[i];
	}
	
	solve();

	return 0;
}