用的 @ANIG 的做法，但是 ta 讲得不是很清楚，所以来扩写一下题解。

令 $f_{l,r}$ 表示区间 $[l,r]$ 的答案，直接区间 DP 是容易的，用决策单调性可以做到 $O(n^2)$。

但是区间 DP 的下限复杂度显然为 $O(n^2)$ 没有前途，考虑拆分贡献。

令 $g_{i,k}$ 表示使得 $f_{l,i}\leq k$ 的最小 $l$，当 $a_i>k$ 时令 $g_{i,k}=i+1$。

这样 $ans=\sum_{k=0}^{upV}\sum_{i-1}^n(g_{i,k}-1)$，$upV$ 为答案值域，上界为 $V+\lceil\log n\rceil$。

为什么上界是这个？考虑极端情况 $a_i$ 全部 $=V$ 时，最优策略是分治下去然后每次合并两个分治区间，分治的层数至多为 $\lceil\log n\rceil$，每层答案增加 $1$，所以上界 $V+\lceil\log n\rceil$。

从小到大枚举 $k$，当 $k=a_i$ 时有 $g_{i,k}=i$。

当 $k\neq a_i$ 时有 $g_{i,k}=g_{g_{i,k-1}-1,k-1}$，即在当前段前面找一段最长的 $\leq k-1$ 的合并起来。

在线段树里面维护 $s_i=g_{i,k}-1$ 的值，这样过后 $k\neq a_i$ 时相当于让 $s_i$ 变成 $s_{s_i}$，当 $s_i\neq s_{s_i}$ 时有意义，考虑维护哪些 $i$ 满足 $s_i\neq s_{s_i}$，可以把 $s_i\neq s_{s_i}$ 的 $s_i$ 扔到 vector 记录下来，由于 $s$ 序列单调，要用的时候可以直接线段树二分找出来是哪段区间。

修改 $s_i\leftarrow s_{s_i}$ 时直接线段树区间覆盖，再看新的 $s_i$ 要不要扔到 vector 里去,$a_i=k$ 的地方修改过后因为 $s_i$ 从 $i$ 变为了 $i-1$，所以原本 $s_j=i$ 的地方后续都要跟着 $s_i$ 一起往前跳，$i$ 和 $i-1$ 都应该扔进 vector 里去。

模拟实现上述过程，在每个 $k$ 累加线段树维护出的答案，就能解决本题。

#include<bits/stdc++.h>
using namespace std;
#define N 1200005
#define int long long
#define all(v) v.begin(),v.end()
int n,m,ans,a[N];vector<int> dif,v[N];
struct Segment_tree{
	int tr[N],mx[N],len[N],tag[N];
	void build(int l=0,int r=n+1,int p=1){
		len[p]=r-l+1,tag[p]=-1;
		if(l==r)  return tr[p]=mx[p]=l,void();
		int mid=(l+r)>>1,ls=p<<1,rs=p<<1|1;
		build(l,mid,ls),build(mid+1,r,rs);
		tr[p]=tr[ls]+tr[rs],mx[p]=max(mx[ls],mx[rs]);
	}
	void pushdown(int &p,int &ls,int &rs){
		if(tag[p]==-1)  return;
		work(ls,tag[p]),work(rs,tag[p]),tag[p]=-1;
	}
	int query(int x,int l=0,int r=n+1,int p=1){
		if(l==r)  return tr[p];
		int mid=(l+r)>>1,ls=p<<1,rs=p<<1|1;pushdown(p,ls,rs);
		return x<=mid?query(x,l,mid,ls):query(x,mid+1,r,rs);
	}
	int bound(int x,int l=0,int r=n+1,int p=1){
		if(l==r)  return l;
		int mid=(l+r)>>1,ls=p<<1,rs=p<<1|1;pushdown(p,ls,rs);
		return mx[ls]>=x?bound(x,l,mid,ls):bound(x,mid+1,r,rs);
	}
	void cover(int sl,int sr,int x,int l=0,int r=n+1,int p=1){
		if(sl<=l&&r<=sr)  return work(p,x);
		int mid=(l+r)>>1,ls=p<<1,rs=p<<1|1;pushdown(p,ls,rs);
		if(sl<=mid)  cover(sl,sr,x,l,mid,ls);
		if(sr>mid)  cover(sl,sr,x,mid+1,r,rs);
		tr[p]=tr[ls]+tr[rs],mx[p]=max(mx[ls],mx[rs]);
	}
	void work(int &p,int &x){tr[p]=x*len[p],mx[p]=tag[p]=x;}
}SGT;
signed main(){
	ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
	cin>>n,SGT.build();
	for(int i=1;i<=n;i++)  cin>>a[i],m=max(m,a[i]+30);
	for(int i=1;i<=n;i++)  v[a[i]].push_back(i),ans+=i;
	for(int i=1;i<=m;i++,ans+=SGT.tr[1]){
		vector<int> tmp;
		vector<tuple<int,int,int>> cov;
		sort(all(dif)),dif.resize(unique(all(dif))-dif.begin());
		for(auto it:dif){
			int l=SGT.bound(it),r=SGT.bound(it+1)-1,x=SGT.query(it);
			cov.emplace_back(l,r,x),tmp.push_back(x);
		}
		for(auto [l,r,x]:cov)  SGT.cover(l,r,x);
		dif.clear();
		for(auto x:tmp)  if(SGT.query(x)!=x)  dif.push_back(x);
		for(auto x:v[i]){
			if(SGT.query(x)<x)  continue;
			SGT.cover(x,x,x-1),dif.push_back(x);
			if(SGT.query(x-1)!=x-1)  dif.push_back(x-1);
		}
	}
	cout<<ans-(n+1)*m<<"\n";
}