言い換え

\(0\) 以上 \(k\) 以下の整数をすべて \(1\) 個以上含む区間の集合を \(S_k\) とおきます．明らかに \(k \geq N\) のとき \(S_{k} = \emptyset\) です．

このとき，\(\displaystyle \mathrm{mex}(\{A_l, \cdots, A_r\}) = \sum_{k=0}^{N-1} \mathrm{haveall}_k([l,r])\) です．ここで．\(\mathrm{haveall}_k([l,r]) := \begin{cases} 1 & ([l,r] \in S_k) \\ 0 & ([l,r] \notin S_k) \end{cases}\) とします．

よって，答えとなる値は \(\displaystyle \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|\) と式変形できるので，\(k = 0,\dots,N-1\) における \(S_k\) の要素数を求めれば十分です．

\(S_k\) の要素数の計算

\(l=1,\dots,N\) に対して \(\displaystyle \mathrm{next}_m[l] := \min_{r \geq l} \left\{\ r\ \middle|\ A_r = m\ \right\} \cup \{N+1\}\) とします．また，\(\displaystyle \mathrm{maxnext}_k[l] := \max_{0 \leq m \leq k} \mathrm{next}_m[l]\) とします．

このとき，\([l,r] \in S_k\) は \(\displaystyle \mathrm{maxnext}_k[l] \leq r \leq N\) と同値であり，これを満たす \([l,r]\) の個数は \(\displaystyle \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]\) です．

したがって，\(k = 0, \dots, N-1\) の昇順に，\(\mathrm{maxnext}_{k-1}[l]\) (\(1 \leq l \leq N\)) から \(\mathrm{maxnext}_k[l]\) (\(1 \leq l \leq N\)) を求めて管理し，その総和を求めることができれば十分です．

\(\mathrm{maxnext}_{k-1}[l]\) から \(\mathrm{maxnext}_k[l]\) を求める

\(\mathrm{maxnext}_k[l] = \max\left(\mathrm{maxnext}_{k-1}[l],\ \mathrm{next}_k[l]\right)\) です．

\(A_x = k\) である \(x\) を昇順に \(x_1, \dots, x_{c}\) とし，番兵として \(x_0 := 0,\ x_{c+1} := N+1\) をおいたとき，\(1 \leq i \leq c+1\) について \(\mathrm{next}_{k}[x_{i-1} + 1] = \dots = \mathrm{next}_{k}[x_i] = x_{i}\) です．

以上より，以下の各クエリをそれぞれ \(O(N)\) 回処理すればよいです．

• \(\mathrm{maxnext}\) の区間 chmax
• \(\mathrm{maxnext}\) の総和を求める

どの \(k\) についても，その \(k\) に対応する区間 chmax クエリをすべて処理した時点で \(\mathrm{maxnext}\) は広義単調増加になっています．よって，区間 \([x_{i-1}+1,\ x_i]\) への chmax クエリは以下のように書けます．

• 要素が広義単調増加である区間 \([x_{i-1}+1,\ x_i]\) 内において，\(\mathrm{maxnext}[r] \geq x_i\) を満たす最小の \(r\) を求める．
• 区間 \(\left[x_{i-1}+1,\ r\right)\) の要素をすべて \(x_i\) に変更する．

したがって，二分探索・区間代入・全体和クエリが高速に処理できればよく，これは一般的な遅延評価セグメント木を使えば実現できます．あるいは，クエリで与えられる区間の性質を利用することで，std::map と同程度の検索能力を持つ平衡二分木で処理することもできます．

いずれにしても，時間計算量は \(O(N \log N)\) です．

実装例 (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;
}