#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int MAXN = 75e4;
const ll INF = 1e18;
struct Data
{
int l, r, p;
};
int N, Q;
ll A[MAXN+10];
Data B[MAXN+10];
ll ans[MAXN+10];
ll val[MAXN+10];
int M;
pii C[MAXN+10];
struct SEG
{
int tree[MAXN*4+10];
void init(int node, int tl, int tr)
{
if(tl==tr)
{
tree[node]=C[tl].second-C[tl].first+1;
return;
}
int mid=tl+tr>>1;
init(node*2, tl, mid);
init(node*2+1, mid+1, tr);
tree[node]=max(tree[node*2], tree[node*2+1]);
}
int query(int node, int tl, int tr, int l, int r)
{
if(l>r) return 0;
if(l<=tl && tr<=r) return tree[node];
if(r<tl || tr<l) return 0;
int mid=tl+tr>>1;
return max(query(node*2, tl, mid, l, r), query(node*2+1, mid+1, tr, l, r));
}
}seg;
vector<ll> ret;
vector<ll> minimum_costs(vector<int> _H, vector<int> _L, vector<int> _R)
{
N=_H.size(); Q=_L.size();
for(int i=1; i<=N; i++) A[i]=_H[i-1];
for(int i=1; i<=Q; i++) B[i]={_L[i-1]+1, _R[i-1]+1, i};
A[0]=2; A[N+1]=2;
vector<pii> V;
for(int i=1; i<=N; i++)
{
if(A[i-1]==2 && A[i]==1) V.push_back({i, 0});
if(A[i]==1 && A[i+1]==2) V.back().second=i;
}
return ret;
M=V.size();
for(int i=1; i<=M; i++) C[i]=V[i-1];
C[0]=pii(0, 0); C[M+1]=pii(N+1, N+1);
seg.init(1, 1, M);
for(int i=1; i<=Q; i++)
{
int l, r;
l=lower_bound(C+1, C+M+1, pii(B[i].l, 0), [&](const pii &p, const pii &q)
{
return p.first<q.first;
})-C;
r=upper_bound(C+1, C+M+1, pii(0, B[i].r), [&](const pii &p, const pii &q)
{
return p.second<q.second;
})-C-1;
int t=seg.query(1, 1, M, l, r);
int tl=max(B[i].l, C[l-1].first), tr=min(B[i].r, C[l-1].second);
t=max(t, tr-tl+1);
tl=max(B[i].l, C[r+1].first), tr=min(B[i].r, C[r+1].second);
t=max(t, tr-tl+1);
ans[B[i].p]=2*(B[i].r-B[i].l+1)-t;
}
/*
for(int i=1; i<=Q; i++)
{
for(int j=B[i].l; j<=B[i].r; j++) val[j]=-A[j];
ll t=0;
vector<int> S;
S.push_back(B[i].l-1);
for(int j=B[i].l; j<=B[i].r; j++)
{
while(S.size()>1 && A[S.back()]<=A[j])
{
t-=A[S[S.size()-1]]*(S[S.size()-1]-S[S.size()-2]);
S.pop_back();
}
t+=A[j]*(j-S.back());
S.push_back(j);
val[j]+=t;
}
t=0;
S.clear();
S.push_back(B[i].r+1);
for(int j=B[i].r; j>=B[i].l; j--)
{
while(S.size()>1 && A[S.back()]<=A[j])
{
t-=A[S[S.size()-1]]*(S[S.size()-2]-S[S.size()-1]);
S.pop_back();
}
t+=A[j]*(S.back()-j);
S.push_back(j);
val[j]+=t;
}
ans[i]=INF;
for(int j=B[i].l; j<=B[i].r; j++) printf("%lld ", val[j]); printf("\n");
for(int j=B[i].l; j<=B[i].r; j++) ans[i]=min(ans[i], val[j]);
}
*/
for(int i=1; i<=Q; i++) ret.push_back(ans[i]);
return ret;
}
