少人做的好题！
这里提供主席树的做法。

题意概况

给定一个序列 $h_{1}, h_{2}, \ldots, h_{N}$，
每次都选出三元组 $(i, j, k)$ 满足 $1 \leq i<j<k \leq N$ 且 $h_{i}>h_{j}<h_{k}$。
然后，将 $h_j$ 增加 $1$，所需代价为 $h_i + h_j + h_k$。
求：在若干次操作之后，让序列 $h$ 满足 $h_1 \leq h_2 \leq \ldots \leq h_p \geq \ldots \geq h_N$ 的最小代价。

思路

我们设 $l$ 是满足当前 $h_1 \leq h_2 \leq \ldots \leq h_l$ 的最大值，$r$ 为满足 $h_r \geq \ldots \geq h_{N-1} \geq h_N$ 的最小值。
我们很容易发现，每次都是选择区间 $[l,r]$ 的最小值来更新。（下面的加粗的“最小值”都是这个意思）

单个最小值简单。
但此时如果有多个最小值，该以怎样的顺序来更新呢？

举个例子： $1\ 3\ 4\ 2\ 3\ 2\ 5\ 2\ 3\ 2\ 1$
红色柱子即此时需要修改的最小值

有一种最优的操作方案：先更新区间 $[i,j]$ 中最左和最右的最小值，再更新中间的最小值。

为什么
我们每次都是选出最小值来更新，先更新最左和最有右的最小值，再跟新中间的，左边大于最小值的最小值和右边大于最小值的最小值都变为了 $x+1$，那么一次更新的最小代价就为 $3x+2$，能保证这是最优的方案（下面有 $x$ 的定义）。

我们不妨设这个最小值为 $x$，有 $k$ 个最小值，最左边的最小值编号为 $L$，最右边为 $R$。

我们称二元组 $(q,p)$ 为 $i$ 的最好二元组，当且仅当满足 $q < i < p$ 且 $h_q$ 是满足 $h_q > h_i$ 的最小值，$h_p$ 同理，也是满足 $h_p > h_i$ 的最小值。

我们先找到 $L$ 和 $R$ 的最好二元组 $(q_L,p_L)$ 和 $(q_R,p_R)$。

我们考虑先修改 $h_L$ 的值，再修改 $h_R$ 的值，最后修改中间的最小值，其代价为

$$(h_{q_L} + h_{p_L} + x) + (x + 1 + h_{p_R} + x) + (k - 2) \times (x + 1 + x + 1 + x)$$

化简为

$$h_{q_L} + h_{p_L} + h_{p_R} + 2k - 3 + (3k - 3)x$$

我们还可以先修改 $h_R$ 的值。
所以将所有最小值增加 $1$ 的最小代价为

$$h_{q_L} + \min(h_{p_L}, h_{q_R}) + h_{p_R} + 2k - 3 + (3k - 3)x$$

我们发现公式中 $\min(h_{p_L}, h_{q_R})$ 查询的范围包括了整个序列 $h$，那么返回的值一定是大于 $x$ 的最小值，即次小值。

设 $y$ 为当前的次小值， 那么将所有最小值增加到次小值的最小代价为

$$(h_{q_L} + h_{p_R} + y + 2k - 3)(y - x) + (3k - 3) \times \frac{(x + y - 1)(y - x)}{2}$$

优化

我们再离散化一下，就可以做到 $O(n^2)$ 了。
至于最小值和 $L$，$R$，可以用 set 来维护，求区间大于某值的最小值是主席树的模板题。

诶？为什么不用修改值呢？

我们每次查询都只查找比最小值大的数，所以改不改值都没影响，维护 $l,r$ 和 set 时只要将小于 $x$ 的数当成 $x$ 就行了。

诶？公式里有个除 $2$，有没有不用逆元就可以处理的方法？

有的有的，将模数 $10^6+3$ 开成 $2 \times 10^6+6$，再在最后结果模回 $10^6+3$ 就行了。 ~( •̀ ω •́ )耶，又少写几行代码~

故最终时间复杂度就为 $O(n \log_2 n)$。

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+100,oo=0x3f3f3f3f,mod=2e6+6;
ll n,ans,top,tot;
int h[N];
ll f[N];
struct node{
	int l,r,s;
};
node t[N*60];
int rt[N];
vector<int> va[N];
set<int> st; 
void lsh(int a[]){
	map<int,int> mp;
	for(int i=1;i<=n;i++) mp[a[i]];
	for(auto &it:mp)
		it.second=++tot,f[tot]=it.first%mod;
	for(int i=1;i<=n;i++) a[i]=mp[a[i]];
}
inline int clone(int v){
	t[++top]=t[v];
	return top;
}
int build(int v,int tl,int tr){
	v=++top;
	if(tl==tr) t[v].s=0;
	else{
		int tm=(tl+tr)>>1,&L=t[v].l,&R=t[v].r;
		L=build(L,tl,tm),R=build(R,tm+1,tr);
		t[v].s=t[L].s+t[R].s;
	}
	return v;
}
inline int update(int v,int tl,int tr,int x){
	v=clone(v);
	if(tl==tr) t[v].s++;
	else{
		int tm=(tl+tr)>>1,&L=t[v].l,&R=t[v].r;
		if(x<=tm) L=update(L,tl,tm,x);
		else R=update(R,tm+1,tr,x);
		t[v].s=t[L].s+t[R].s;
	}
	return v;
}
inline int ask(int u,int v,int tl,int tr,int k){
	if(tl==tr) return tl>=k?tl:oo;
	int tm=(tl+tr)>>1;
	int lcnt=t[t[v].l].s-t[t[u].l].s;
	if(lcnt&&k<=tm){
		int res=ask(t[u].l,t[v].l,tl,tm,k);
		if(res!=oo) return res;
	}
	int rcnt=t[t[v].r].s-t[t[u].r].s;
	if(!rcnt) return oo;
	return ask(t[u].r,t[v].r,tm+1,tr,k);
}
inline void add(int x,const int& y,const int& l,const int& r){
	while(x<y){
		x++;
		for(int v:va[x]) if(v>=l&&v<=r) st.insert(v);
	}
}
inline void cheak(const int &l,const int &r){
	while(!st.empty()&&*st.begin()<l) st.erase(st.begin());
	while(!st.empty()&&*st.rbegin()>r) st.erase(prev(st.end()));
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++) cin>>h[i];
	lsh(h);
	rt[0]=build(rt[0],1,tot);
	for(int i=1;i<=n;i++) va[h[i]].push_back(i);
	for(int i=1;i<=n;i++) rt[i]=update(rt[i-1],1,tot,h[i]);
	int l=1,r=n,x=0;
	while(1){
		while(l<r&&max(x,h[l+1])>=h[l]) l++;
		while(l<r&&max(x,h[r-1])>=h[r]) r--;
		if(!(l+1<r)) break;
		cheak(l,r);
		int k=st.size();
		if(k==0){
			add(x,x+1,l,r),x++;
			continue;
		}
		int L=*st.begin(),R=*st.rbegin();
		int qL=ask(rt[0],rt[L],1,tot,x+1);
		int pR=ask(rt[R-1],rt[n],1,tot,x+1);
		int V=x+1;
		ll num=(f[V]-f[x]+mod)%mod;
		ll H=(f[x]+f[V]-1)*num/2%mod;
		if(k==1) ans=(ans+(f[qL]+f[pR])*num+H)%mod;
		else ans=(ans+(f[qL]+f[pR]+f[V]+2*k-3+mod)*num+H*(3*k-3))%mod;
		add(x,V,l,r),x=V;
	}
	cout<<ans%int(1e6+3);
	return 0;
}