通过简单的观察不难发现，对于一个元素不重的数组，它的权值等价于它含的元素从 开始连续增加的最长长度。例如，对于数组 ，从 开始往大一个一个数，最多能数到 ，那么它的权值就是 。

通过这个观察结果，我们不难想到，只有当一个数组含元素 的时候，才开始记录权值。那么，我们的思路就围绕着数字 展开。

对于一个数组 （当然这里的 的前面或后面也可以没有元素），不包含数字 的子数组就可以直接跳过，我们不妨考虑以 结尾的子数组的权值，这样考虑的话就要从数字 出现的位置开始往后考虑，我们要枚举子数组结束的地方，不妨考虑倒着枚举，先把所有以数字 及其左边所有数开头， 结尾的子数组的权值加入一个数组（这里记作 ），现在倒着加入这些权值。

对于计算权值，我们可以考虑开一个辅助数组 并设定一个辅助变量 ，初始化 ，每次加入一个元素 ，都把 标记一下，然后当 的下一位被标记过时一直递增 ，最终的 就是当前子数组的权值。

加入所有的权值后， 数组里的值一定是单调不减的，这样我们再考虑删除右端点，从后往前一个个删，直到删掉数字 ，每次删掉，都让 和删除的元素取小，这就是剩余子数组权值的上限， 数组里大于等于 的权值都可以和 取小（因为 被删除了，权值取不到 ），小于的则可以保留，小于部分的求和可以通过前缀和优化，而找 数组里大于等于 的第一个位置可以通过 实现，时间复杂度

代码：

//Code from Whalica
#include<bits/stdc++.h>

using i64 = long long;
using u64 = unsigned long long;

void solve() {
	int n;
	std::cin >> n;
	
	std::vector<int> a(n + 1);
	//数字1的位置 
	int pos;
	for (int i = 1; i <= n; i++) {
		std::cin >> a[i];
		if (a[i] == 1) {
			pos = i;
		}
	}
	
	//以数字1及其左边的数字开头，以a[n]结尾的所有子数组的权值 
	std::vector<i64> sum(1);
	//用来算权值的辅助数组 
	std::vector<int> f(n + 1); 
	int max = 0;
	//先算一遍数字1出现的位置到a[n]的权值 
	for (int i = n; i > pos; i--) {
		f[a[i]]++;
		while (f[max + 1]) {
			max++;
		}
	}
	
	i64 ans = 0;
	//再在原来的基础上往左扩展左端点
	for (int i = pos; i >= 1; i--) { 
		f[a[i]]++;
		while (max + 1 <= n && f[max + 1]) {
			max++;
		}
		//提前把权值加上 
		ans += max;
		sum.push_back(max);
	}
	
	//处理前缀和
	std::vector<i64> pre(sum.size());
	for (int i = 1; i < sum.size(); i++) {
		pre[i] = pre[i - 1] + sum[i];
	}
	
	for (int i = n; i > pos; i--) {
		//删除右端点，缩小上界 
		max = std::min(max, a[i]);
		//找到sum数组中从左往右第一个大于等于max的位置 
		int p = std::lower_bound(sum.begin() + 1, sum.end(), max) - sum.begin(); 
		
		//sum数组中小于max的权值可以完全保留，大于等于的权值只能取max - 1 
		ans += pre[p - 1] + 1LL * (sum.size() - p) * (max - 1);
	}
	
	std::cout << ans << "\n";
}

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

	int t = 1;
//	std::cin >> t;

	while (t--) {
		solve();
	}

	return 0;
}