#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define INF LLONG_MAX
ll pre[5001][5001],suf[5001][5001];
ll cum[5001][5001],cum2[5001][5001];
int st[400002],st2[400002],st3[400002];
vector<int> A,tab;
void build(int node,int l,int r){
if(l==r){
st[node]=l;
st3[node]=tab[l];
return ;
}
int med=(l+r)/2;
build(node*2,l,med),build(node*2+1,med+1,r);
if(A[st[node*2+1]]>=A[st[node*2]])st[node]=st[node*2+1];
else st[node]=st[node*2];
st3[node]=max(st3[node*2],st3[node*2+1]);
}
void build2(int node,int l,int r){
if(l==r){
st2[node]=l;
return ;
}
int med=(l+r)/2;
build2(node*2,l,med),build2(node*2+1,med+1,r);
if(A[st2[node*2]]>=A[st2[node*2+1]])st2[node]=st2[node*2];
else st2[node]=st2[node*2+1];
}
int query(int node,int l,int r,int i,int j){
if(l>j||r<i)
return -1;
if(l>=i&&r<=j){
if(A[st[node]]<2)return -1;
return st[node];
}
int med=(l+r)/2;
int idx=query(node*2+1,med+1,r,i,j);
if(idx!=-1)return idx;
return query(node*2,l,med,i,j);
}
int query2(int node,int l,int r,int i,int j){
if(l>j||r<i)
return -1;
if(l>=i&&r<=j){
if(A[st2[node]]<2)return -1;
return st2[node];
}
int med=(l+r)/2;
int idx=query2(node*2,l,med,i,j);
if(idx!=-1)return idx;
return query2(node*2+1,med+1,r,i,j);
}
int query3(int node,int l,int r,int i,int j){
if(l>j||r<i)
return -1;
if(l>=i&&r<=j)
return st3[node];
int med=(l+r)/2;
return max(query3(node*2,l,med,i,j),query3(node*2+1,med+1,r,i,j));
}
vector<ll> minimum_costs(vector<int> H, vector<int> L,vector<int> R) {
int n=H.size();
if(n<=5000){
for (int i = 0; i < n; ++i)
for (int j = i; j < n;++j)
{
pre[i][j]=H[j];
if(j)pre[i][j]=max(pre[i][j],pre[i][j-1]);
}
for (int i = n-1; i >= 0; i--)
for (int j = i; j >= 0;j--)
{
suf[i][j]=H[j];
if(j!=(n-1))suf[i][j]=max(suf[i][j],suf[i][j+1]);
}
for (int i = 0; i < n; ++i)
for (int j = 0; j < n; ++j)
{
cum2[i][j]+=suf[i][j];
if(i)cum2[i][j]+=cum2[i-1][j];
cum[i][j]+=pre[i][j];
if(i)cum[i][j]+=cum[i-1][j];
}
int Q = L.size();
vector<ll> C(Q);
for (int q = 0; q < Q; ++q) {
ll ans=INF;
for (int i = L[q]; i <=R[q] ; ++i)
ans=min(ans,cum2[R[q]][i]+cum[n-1][i]-(L[q]?cum[L[q]-1][i]:0)-H[i]);
C[q]=ans;
}
return C;
}
A=H;
tab.resize(n);
int prev=n-1;
for (int i = n-1; i >=0 ; i--)
{
if(H[i]==1)tab[i]=-1;
else{
tab[i]=prev-i-((H[prev]==2)?1:0);
prev=i;
}
}
build(1,0,n-1);
build2(1,0,n-1);
int Q = L.size();
vector<ll> C(Q);
for (int q = 0; q < Q; ++q) {
int lefty=query2(1,0,n-1,L[q],R[q]),righty=query(1,0,n-1,L[q],R[q]);
//cerr<<lefty<<" "<<righty<<"\n";
if(lefty==-1){
C[q]=R[q]-L[q]+1;
continue;
}
C[q]=INF;
if(abs(lefty-righty)<=1)C[q]=min(C[q],(ll)(2*(R[q]-L[q]+1)));
else {
int nb=query3(1,0,n-1,lefty,righty-1);
C[q]=min(C[q],(ll)(nb+2*(R[q]-L[q]+1-nb)));
}
if(righty!=R[q]){
righty++;
C[q]=min(C[q],(ll)(R[q]-righty+1+2*(righty-L[q])));
}
if(lefty!=L[q]){
lefty--;
C[q]=min(C[q],(ll)((lefty-L[q])+1+2*(R[q]-lefty)));
}
}
return C;
}
