#include "meetings.h"
#include <bits/stdc++.h>
//#include "grader.cpp"
using namespace std;
typedef long long ll;
const ll INF=1e9;
typedef pair<ll,ll> pll;
ll n,q,v[100005],rmq[21][100005],loga[100005];
ll sdist[5005][5005];
ll getmax(ll l,ll r)
{
ll lg=loga[r-l+1];
return max(rmq[lg][l],rmq[lg][r-(1<<lg)+1]);
}
ll nrsecv=0;
struct date
{
ll l,r;
} secv[100005];
set<pll> setik;
std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L,std::vector<int> R)
{
n=H.size();
vector<ll> sol;
q=L.size();
for(int i=1;i<=n;i++)
{
v[i]=H[i-1];
for(int bit=0;bit<=20;bit++)
if((1<<bit)<=i)
loga[i]=bit;
}
if(n<=5000&&q<=5000)
{
for(int i=n;i>=1;i--)
{
rmq[0][i]=v[i];
for(int j=1;j<=20;j++)
{
rmq[j][i]=rmq[j-1][i];
int poz=i+(1<<(j-1));
if(poz<=n)
rmq[j][i]=max(rmq[j][i],rmq[j-1][poz]);
}
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
ll st=min(i,j);
ll dr=max(i,j);
ll val=getmax(st,dr);
sdist[i][j]=sdist[i][j-1]+val;
}
}
for(int z=0;z<q;z++)
{
int l=L[z]+1;
int r=R[z]+1;
ll ans=1e18;
for(int i=l;i<=r;i++)
ans=min(ans,sdist[i][r]-sdist[i][l-1]);
sol.push_back(ans);
}
return sol;
}
for(int i=1;i<=n;i++)
if(v[i]==1)
{
ll r=i;
while(r<=n&&v[r]==1)
r++;
r--;
nrsecv++;
secv[nrsecv]={i,r};
setik.insert({i,r});
i=r;
}
for(int i=nrsecv;i>=1;i--)
{
rmq[0][i]=secv[i].r-secv[i].l+1;
for(int j=1;j<=20;j++)
{
rmq[j][i]=rmq[j-1][i];
int poz=i+(1<<(j-1));
if(poz<=nrsecv)
rmq[j][i]=max(rmq[j][i],rmq[j-1][poz]);
}
}
for(int z=0;z<q;z++)
{
ll l=L[z]+1;
ll r=R[z]+1;
ll st=1;
ll dr=nrsecv;
ll fst=nrsecv+1;
ll best=0;
while(st<=dr)
{
ll mij=(st+dr)/2;
if(secv[mij].l>=l)
{
fst=mij;
dr=mij-1;
}
else
st=mij+1;
}
st=1;
dr=nrsecv;
ll lst=0;
while(st<=dr)
{
ll mij=(st+dr)/2;
if(secv[mij].r<=r)
{
lst=mij;
st=mij+1;
}
else
dr=mij-1;
}
if(fst<=lst)
best=getmax(fst,lst);
if(v[l]==1)
{
auto it=prev(setik.lower_bound({l,INF}));
ll rgt=min(r,(*it).second);
best=max(best,rgt-l+1);
}
if(v[r]==1)
{
auto it=prev(setik.lower_bound({r,INF}));
ll lft=max(l,(*it).first);
best=max(best,r-lft+1);
}
sol.push_back(2LL*(r-l+1)-best);
}
return sol;
}
