沒有看懂簡潔寫法/ll 于是學了官方題解的做法。語言拙劣，隨意記錄。

首先有一種基本的決策，就是把一個方塊就地埋葬。用一次操作把兩列拉開形成一個空位，再用一次操作把這個空位填上。

埋葬一個方塊的代價是 \(2\)。

其實在一些情況下會有更優的方案，比如最右邊一列，直接扔到右邊的空地上明顯比就地埋葬要好，因為這樣解決單個方塊只需要 \(1\) 的代價。我們稱這種操作為推平吧。

所以我們最終的策略是，一些塊往左推平，一些塊往右推平，一些塊就地埋葬。最左邊和最右邊是無窮遠，所以過去的一定是一整堆一整堆的（因為推平操作單次更優）。

然后完全想不到的是，官方題解用最短路解決了這題。感覺這題建圖有一點網絡流的意思（？）

先建立超級源匯 \(S,T\) 表示左邊和右邊的無窮遠。本來是要給每個方塊一個編號的，但這樣就爆炸了，所以先給沒堆底部和頂部各一個編號。本文中每堆的流動方向是從底部到頂部。

下面開始建有向圖，有點繞的。

• \(S\) 向每個堆頂連一條邊，邊權是前綴和 \(pre_i\)，表示最左邊的連續堆的推平操作，直接把左邊的堆解決掉了（所以是連堆頂）。
• 同理，每個堆的底部和 \(T\) 連一條權值為后綴和 \(suf_i\) 的邊。
• \(i\) 的堆頂連接 \(i+1\) 的底部，把相鄰兩堆連接起來。
• 每個堆的堆底向堆頂連一條權值為 \(2 \times a_i\) 的邊，意思是我們用 \(2\) 的單位代價解決掉一整堆。
• 單個塊推平的建邊。

接下來就是最麻煩的單個方塊推平到空位的建圖。

假設現在在考慮向右推平：

• 如果當前位置為空，如果棧中有未匹配的方塊，就匹配。
• 如果當前位置塊數大于 \(1\)，那么入棧。

所以就可以對每一堆求出如果向右推平，會推到哪些空位，給每堆開一個 \(vector\) 存位置就可以了，因為空位數最多是 \(O(n)\) 的，所以空間復雜度是對的。

同理，我們可以求出如果向左推平，每堆會匹配哪些位置。

我們可能會用到一些單個方塊，可是之前建點都是整堆的。給每個塊開編號是不現實的，而有用的（匹配上的）點只有上文提到的 \(O(n)\) 個，所以相當于是要在堆中建一些切割點，把堆分裂開。

分裂開之后再和對應的匹配位置連邊（邊權為坐標差）就可以了。另外，因為我們分裂了一些點，而最開始的單個埋葬的決策是從堆底連到堆頂的，所以我們需要對每堆相鄰的分裂點連邊，邊權為它們之間夾著的方塊數再乘 \(2\)。

離散化的細節還是比較多的。

最后只需要對 \(S\) 到 \(T\) 跑最短路就可以了。

#include<bits/stdc++.h>
#define fi first
#define se second
#define For(i,il,ir) for(int i=(il);i<=(ir);++i)
#define Rof(i,ir,il) for(int i=(ir);i>=(il);--i)
using namespace std;
typedef long long ll;
typedef pair<ll,int> pli;
typedef pair<int,int> pii;
const int N=1e6+10;

int n;
ll a[N],pre[N],suf[N];

int head[N<<2],cnt=1;
struct edge{
    ll w;
    int v,nxt;
}e[N<<2];
void add(int x,int y,ll z){ e[cnt].v=y,e[cnt].w=z,e[cnt].nxt=head[x],head[x]=cnt++; }

int idtot,S,T;
ll dis[N<<1];
bool vis[N<<1];
priority_queue<pli,vector<pli>,greater<pli> > q;

ll Dijkstra(){
    memset(dis,0x3f,sizeof(dis));
    dis[S]=0,q.push(make_pair(0,S));
    while(!q.empty()){
        int u=q.top().se; q.pop();
        if(vis[u]) continue;
        vis[u]=true;

        for(int i=head[u];i;i=e[i].nxt){
            int v=e[i].v;
            if(dis[v]>dis[u]+e[i].w)
                dis[v]=dis[u]+e[i].w,q.push(make_pair(dis[v],v));
        }
    }
    return dis[T];
}

stack<int> st;
vector<int> lft[N],rgt[N];
int num[N],h[N<<1],g[N<<1],ht;

int gettop(){ int j=st.top();if(!--num[j]) st.pop(); return j; }
signed main()
{
    scanf("%d",&n);
    For(i,1,n) scanf("%lld",&a[i]);
    S=n+n+1,idtot=T=n+n+2;

    add(S,1,0);
    For(i,1,n) add(i,i+n,max(a[i]-1,0ll)*2);// 埋葬第 i 堆
    For(i,1,n-1) add(i+n,i+1,0);// i 的 top 和 i+1 的 bottom
    add(n+n,T,0);

    For(i,1,n) pre[i]=pre[i-1]+a[i],add(S,i+n,max(pre[i]-1,0ll));//推平一個前綴
    Rof(i,n,1) suf[i]=suf[i+1]+a[i],add(i,T,max(suf[i]-1,0ll));//推平一個后綴
    
    For(i,1,n)
        if(a[i]>1) num[i]=a[i]-1,st.push(i);
        else if(!a[i] && !st.empty()) rgt[gettop()].push_back(i);
    while(!st.empty()) st.pop();
    Rof(i,n,1)
        if(a[i]>1) num[i]=a[i]-1,st.push(i);
        else if(!a[i] && !st.empty()) lft[gettop()].push_back(i);

    For(i,1,n) if(a[i]>1)//補到空列（離散化）
    {
        ht=0,h[0]=0,g[0]=i;
        reverse(rgt[i].begin(),rgt[i].end());
        
        int tot=0;
        for(int p:lft[i]) h[++ht]=++tot,g[ht]=++idtot,add(p,g[tot],i-p);
        tot=a[i]-rgt[i].size()-2;
        

        for(int p:rgt[i])
            if(++tot<=ht) add(g[tot],p+n,p-i);
            else h[++ht]=tot,g[ht]=++idtot,add(g[ht],p+n,p-i);
        h[++ht]=a[i]-1,g[ht]=i+n;
        For(j,0,ht-1)
            add(g[j],g[j+1],2ll*(h[j+1]-h[j]));
    }
    printf("%lld\n",Dijkstra());
    return 0;
}