M求调

#include<bits/stdc++.h>
#define int long long
using namespace std;
int a[200010];
int per[200010],suf[200010];
struct ppp
{
    int l,r;
    int maxn,minn;
    int lazy;
}tree[400010],tr[400010];
void up(int i)
{
    tree[i].maxn=max(tree[i*2].maxn,tree[i*2+1].maxn);
    tree[i].minn=min(tree[i*2].minn,tree[i*2+1].minn);
    tr[i].maxn=max(tr[i*2].maxn,tr[i*2+1].maxn);
    tr[i].minn=min(tr[i*2].minn,tr[i*2+1].minn);
}
void build(int i,int l,int r)
{
    tree[i].l=l;
    tree[i].r=r;
    tr[i].l=l;
    tr[i].r=r;
    if(l==r)
    {
        tree[i].maxn=a[l];
        tree[i].minn=a[l];
        tr[i].maxn=a[l];
        tr[i].minn=a[l];
        return;
    }
    int mid=(r+l)>>1;
    build(2*i,l,mid);
    build(2*i+1,mid+1,r);
    up(i);
}
void down(int i)
{
    if(tree[i].lazy==1)
    {
        tree[i*2].lazy=1;
        tree[i*2+1].lazy=1;
        tree[i*2].maxn*=2;
        tree[i*2].minn*=2;
        tree[i*2+1].maxn*=2;
        tree[i*2+1].minn*=2;
        tree[i].lazy=0;
    }
}
void change(int i,int l,int r)
{
    if(l<=tree[i].l&&r>=tree[i].r)
    {
        tree[i].maxn=tr[i].maxn*2;
        tree[i].minn=tr[i].minn*2;
        return;
    }
    down(i);
    int mid=(tree[i].l+tree[i].r)>>1;
    if(l<=mid)
    change(2*i,l,r);
    if(r>mid)
    change(2*i+1,l,r);
    up(i);
}
int askmi(int i,int l,int r)
{
    if(l<=tree[i].l&&r>=tree[i].r)
    {
        return tree[i].minn;
    }
    down(i);
    int minn=3e18;
    int mid=(tree[i].l+tree[i].r)>>1;
    if(l<=mid)
    minn=min(minn,askmi(2*i,l,r));
    if(r>mid)
    minn=min(minn,askmi(i*2+1,l,r));
    up(i);
    return minn;
}
int askma(int i,int l,int r)
{
    if(l<=tree[i].l&&r>=tree[i].r)
    {
        return tree[i].maxn;
    }
    down(i);
    int minn=0;
    int mid=(tree[i].l+tree[i].r)>>1;
    if(l<=mid)
    minn=max(minn,askma(2*i,l,r));
    if(r>mid)
    minn=max(minn,askma(i*2+1,l,r));
    up(i);
    return minn;
}
signed main()
{
    std::ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int n;
    cin>>n;
    int i;
    int minn=3e18,maxn=0;
    for(i=1;i<=n;i++)
    {
        cin>>a[i];
        minn=min(minn,a[i]);
        maxn=max(maxn,a[i]);
    }
    for(i=1;i<=n;i++)
    {
        if(a[i]==minn)
        per[i]=per[i-1]+1;
        else
        per[i]=per[i-1];
    }
    for(i=n;i>=1;i--)
    {
        if(a[i]==minn)
        suf[i]=suf[i+1]+1;
        else
        suf[i]=suf[i+1];
    }
    for(i=1;i<=n;i++)
    {
        if(a[i]==maxn)
        {
            if(suf[i]>0&&per[i]>0)
            {
                cout<<maxn-minn;
                return 0;
            }
        }
    }
    map<int,int>l,r;
    for(i=1;i<=n;i++)
    {
        if(l[a[i]]==0)
        l[a[i]]=i;
        r[a[i]]=i;
    }
    build(1,1,n);
    sort(a+1,a+1+n);
    int ll=n+1,rr=0;
    int ans=3e18;
    for(i=1;i<=n;i++)
    {
        ll=min(ll,l[a[i]]);
        rr=max(rr,r[a[i]]);
        change(1,ll,rr);
        int xmi=askmi(1,1,n);
        int xma=askma(1,1,n);
        ans=min(ans,xma-xmi);
    }
    int g=0,h=3e18;
    for(i=1;i<=n;i++)
    {
        g=max(g,a[i]*2);
        h=min(h,a[i]*2);
    }
    int count=0;
    for(i=1;i<=n;i++)
    {
        if(a[i]==minn)
        count++;
    }
    if(count>=2)
    ans=min(ans,maxn-minn);
    cout<<min(ans,g-h);
    return 0;
}