#include "meetings.h"
#include <iostream>
using namespace std;
long long int point[5005][5005][2];
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<=500)
{
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
{
std::vector<long long> c(q);
for(int i=0;i<q;i++)
{
long long int len=0,now=0;
for(int j=l[i];j<=r[i];j++)
{
if(h[j]==1)now++;
else
{
len=max(len,now);
now=0;
}
}
len=max(len,now);
c[i]=(r[i]-l[i]+1)*2-len;
}
return c;
}
}
