#include "meetings.h"
#include <iostream>
using namespace std;
long long int point[5005][5005][2],tree[1000005][3],he[1000005],len[1000005],temp[1000005][3],st,en;
int build(int s,int e,int t)
{
if(s==e)
{
if(he[s]==1)
{
tree[t][0]=1;
tree[t][1]=1;
tree[t][2]=1;
}
return 0;
}
else
{
build(s,(s+e)/2,t*2);
build((s+e)/2+1,e,t*2+1);
tree[t][0]=max(tree[t*2][0],max(tree[t*2+1][0],tree[t*2][2]+tree[t*2+1][1]));
if(tree[t*2][1]==(s+e)/2-s+1)
{
tree[t][1]=tree[t*2][1]+tree[t*2+1][1];
}
else tree[t][1]=tree[t*2][1];
if(tree[t*2+1][2]==e-(s+e)/2)
{
tree[t][2]=tree[t*2][2]+tree[t*2+1][2];
}
else tree[t][2]=tree[t*2+1][2];
}
return 0;
}
int find(int s,int e,int t)
{
if(e<st || s>en)
{
temp[t][0]=0;
temp[t][1]=0;
temp[t][2]=0;
len[t]=1;
return 0;
}
if(st<=s && e<=en)
{
temp[t][0]=tree[t][0];
temp[t][1]=tree[t][1];
temp[t][2]=tree[t][2];
len[t]=e-s+1;
return 0;
}
find(s,(s+e)/2,t*2);
find((s+e)/2+1,e,t*2+1);
len[t]=len[t*2]+len[t*2+1];
temp[t][0]=max(temp[t*2][0],max(temp[t*2+1][0],temp[t*2][2]+temp[t*2+1][1]));
if(temp[t*2][1]==len[t*2])
{
temp[t][1]=temp[t*2][1]+temp[t*2+1][1];
}
else temp[t][1]=temp[t*2][1];
if(temp[t*2+1][2]==len[t*2+1])
{
temp[t][2]=temp[t*2][2]+temp[t*2+1][2];
}
else temp[t][2]=temp[t*2+1][2];
return 0;
}
std::vector<long long> minimum_costs(std::vector<int> h, std::vector<int> l, std::vector<int> r) {
int q = l.size();
int n = h.size();
if(n<=5000 && q<=5000)
{
for(int i=0;i<n;i++)
{
int tmp=h[i];
point[i][i][1]=h[i];
for(int j=i+1;j<n;j++)
{
tmp=max(tmp,h[j]);
point[i][j][1]=point[i][j-1][1]+tmp;
}
}
for(int i=n-1;i>=0;i--)
{
int tmp=h[i];
point[i][i][0]=h[i];
for(int j=i-1;j>=0;j--)
{
tmp=max(tmp,h[j]);
point[j][i][0]=point[j+1][i][0]+tmp;
//cout<<i<<" "<<j<<" "<<point[j][i][0]<<" ";
}
//cout<<endl;
}
std::vector<long long> c(q);
for(int i=0;i<q;i++)
{
long long int tmp=999999999999999999;
for(int j=l[i];j<=r[i];j++)
{
if(point[l[i]][j][0]+point[j][r[i]][1]-h[j]<tmp)
{
c[i]=j;
tmp=point[l[i]][j][0]+point[j][r[i]][1]-h[j];
//cout<<tmp<<" "<<j<<" "<<point[l[i]][j][0]<<" "<<point[j][r[i]][1]<<" ";
}
}
c[i]=tmp;
//cout<<endl;
}
return c;
}
else
{
//cout<<"ok"<<endl;
for(int i=0;i<n;i++)he[i]=h[i];
build(0,n-1,1);
//cout<<"ok"<<endl;
std::vector<long long> c(q);
for(int i=0;i<q;i++)
{
st=l[i],en=r[i];
long long int len=0,now=0;
find(0,n-1,1);
c[i]=(r[i]-l[i]+1)*2-temp[1][0];
}
return c;
}
}
