#include <vector>
using namespace std;
int const N=1e5+10;
struct node
{
int msb=0,mp=0,ms=0;
bool valid=0;
};
node St[4*N]={};
node comb(node a,node b)
{
node c;
c.valid=(a.valid&&b.valid);
c.msb=max(a.msb,b.msb);
if (a.ms&&b.mp)
c.msb=max(c.msb,a.ms+b.mp);
c.ms=b.ms;
if (b.valid)
c.ms=max(c.ms,a.ms+b.ms);
c.mp=a.mp;
if (a.valid)
c.mp=max(c.mp,a.mp+b.mp);
return c;
}
void update(int i,int r,int st,int en,int val)
{
if (st==en)
{
if (val==1)
{
St[i].msb=St[i].ms=St[i].mp=St[i].valid=1;
}
return;
}
int mid=(st+en)/2;
if (r<=mid)
update(i*2,r,st,mid,val);
else
update(i*2+1,r,mid+1,en,val);
St[i]=comb(St[i*2],St[i*2+1]);
}
node get(int i,int st,int en,int l,int r)
{
if (st>=l&&en<=r)
return St[i];
if (st>r||en<l)
{
node c;
c.valid=1;
return c;
}
int mid=(st+en)/2;
return comb(get(i*2,st,mid,l,r),get(i*2+1,mid+1,en,l,r));
}
vector<long long> minimum_costs(vector<int> H, vector<int> L,vector<int> R)
{
int n=H.size();
vector<long long>ans(L.size(),1e15);
bool subt3=1;
for (int i=0;i<n;i++)
if (H[i]>2)
subt3=0;
if (subt3)
{
for (int i=0;i<n;i++)
update(1,i,0,n-1,H[i]);
vector<long long>ans;
for (int i=0;i<L.size();i++)
{
node z=get(1,0,n-1,L[i],R[i]);
ans.push_back(2*(R[i]-L[i]+1)-z.msb);
}
return ans;
}
int val[n]={};
long long pre[n+1]={};
for (int i=0;i<n;i++)
{
int mx=H[i];
val[i]=mx;
for (int j=i-1;j>=0;j--)
{
mx=max(mx,H[j]);
val[j]=mx;
}
mx=H[i];
for (int j=i+1;j<n;j++)
{
mx=max(mx,H[j]);
val[j]=mx;
}
for (int j=1;j<=n;j++)
pre[j]=pre[j-1]+val[j-1];
for (int j=0;j<L.size();j++)
{
if (i>=L[j]&&i<=R[j])
ans[j]=min(ans[j],pre[R[j]+1]-pre[L[j]]);
}
}
return ans;
}
