#include "meetings.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pi;
typedef vector<ll> vi;
typedef vector<pi> vpi;
#define mp make_pair
#define pb emplace_back
#define f first
#define s second
#define ALL(x) x.begin(),x.end()
#define SZ(x) (ll)x.size()
#define lb lower_bound
#define ub upper_bound
ll A[100100];
struct SparseTable{
ll N,K;
vector<vpi> ST;
SparseTable(ll _N){
N=_N;K=MSB(N);
ST.resize(K);
for (ll i=0;i<N;++i)ST[0].pb(mp(i,A[i]));
for (ll k=1;k<K;++k){
for (ll i=0;i+(1<<k)<=N;++i){
if (ST[k-1][i].s > ST[k-1][i+(1<<(k-1))].s){
ST[k].pb(ST[k-1][i]);
}
else ST[k].pb(ST[k-1][i+(1<<(k-1))]);
}
}
}
inline int MSB(unsigned int x){return 32-__builtin_clz(x);}
pi query(ll x, ll y){
ll k = MSB(y-x+1)-1;
if (ST[k][x].s > ST[k][y-(1<<k)+1].s)return ST[k][x];
return ST[k][y-(1<<k)+1];
}
}*S;
ll memo[5010][5010];
ll ask(ll x, ll y){
if (memo[x][y] != -1)return memo[x][y];
if (x==y)return memo[x][y] = A[x];
pi tall = S->query(x,y);
// cout<<"Tall "<<tall.f<<' '<<tall.s<<'\n';
// Answer is on one side of tall
if (tall.f == x){
return memo[x][y] = A[x] + ask(x+1,y);
}
if (tall.f == y){
return memo[x][y] = A[y] + ask(x,y-1);
}
ll l = ask(x,tall.f-1);
ll r = ask(tall.f+1,y);
ll ld = tall.f-x+1;
ll rd = y-tall.f+1;
return memo[x][y] = min(ld*tall.s+r, rd*tall.s+l);
}
ll N,Q;
std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L,
std::vector<int> R) {
N = SZ(H);
Q = SZ(L);
std::vector<long long> C(Q);
for (ll j = 0; j < Q; ++j) {
C[j] = -1;
}
if (Q <= 5000){
for (ll i=0;i<N;++i)A[i]=H[i];
S = new SparseTable(N);
memset(memo,-1,sizeof(memo));
for (ll i=0;i<Q;++i){
C[i] = ask(L[i],R[i]);
}
}else{
vpi V,ones,twos;
set<int> ends, starts;
for (int i=0;i<N;++i){
if (SZ(V) == 0 || H[i] != V.back().f){
if (SZ(V)){
if (V.back().f == 1)ones.pb(mp(V.back().s, i-1));
else twos.pb(mp(V.back().s, i-1));
}
V.pb(mp(H[i], i));
}
}
if (V.back().f == 1)ones.pb(mp(V.back().s, N-1));
else twos.pb(mp(V.back().s, N-1));
// cout<<"Ones\n";
// for (auto i : ones)cout<<i.f<<' '<<i.s<<'\n';
// cout<<"Twos\n";
// for (auto i : twos)cout<<i.f<<' '<<i.s<<'\n';
for (auto i : ones){
for (int x=i.f;x<=i.s;++x)A[x] = i.s-i.f+1;
}
S = new SparseTable(N);
for (auto i : ones){
ends.insert(i.s);
starts.insert(i.f);
}
for (int i=0;i<Q;++i){
ll maxlen = 0;
ll l=L[i];
ll r=R[i];
if(A[l] != 0){
ll x = *ends.lb(l);
maxlen = max(maxlen, min(x,r)-l+1);
l=x+1;
}
if(A[r] != 0){
ll x = *(--starts.ub(r));
maxlen = max(maxlen, r-max(l,x)+1);
r=x-1;
}
// cout<<maxlen<<' '<<l<<' '<<r<<'\n';
if (l<=r) maxlen = max(maxlen, S->query(l,r).s);
C[i] = 2*(R[i]-L[i]+1) - maxlen;
}
}
return C;
}
