#include<bits/stdc++.h>
#include "meetings.h"
using namespace std;
#define ll long long
#define f first
#define s second
void setIO(string name="") {
cin.tie(0)->sync_with_stdio(0);
if (!name.empty()) {
freopen((name+".in").c_str(), "r", stdin);
freopen((name+".out").c_str(), "w", stdout);
}
}
struct Tree{
int n=1;
vector<int> vals,l_vals,r_vals,left,right;
vector<int> combine(vector<int> a,vector<int> b){ //val, left, right
vector<int> ans = {max(a[0],max(a[2] + b[1],b[0])),a[1],b[2],0};
if(a[3]) ans[1] = a[0] + b[1];
if(b[3]) ans[2] = a[1] + b[0];
if(a[3] && b[3]) ans[3] = 1;
return ans;
}
Tree(int sz,vector<int> &v){
while(n < sz)n*=2;
vals = l_vals = r_vals = left = right = vector<int>(2*n,0);
for(int i = 0;i<n;i++){
left[i+n] = i;
right[i+n] = i+1;
if(i < sz){
vals[i+n] = v[i] == 1 ? 1 : 0;
l_vals[i+n] = v[i] == 1 ? 1 : 0;
r_vals[i+n] = v[i] == 1 ? 1 : 0;
}
}
for(int i = n-1;i;i--){
left[i] = left[i*2];
right[i] = right[i*2+1];
vector<int> tmp = combine({vals[i*2],l_vals[i*2],r_vals[i*2],vals[i*2] == right[i*2] - left[i*2]},{vals[i*2+1],l_vals[i*2+1],r_vals[i*2+1],vals[i*2+1] == right[i*2 + 1] - left[i*2+1]});
vals[i] = tmp[0];
l_vals[i] = tmp[1];
r_vals[i] = tmp[2];
}
}
int range_query(int l,int r){
//cerr<<"wtfff "<<l<<" "<<r<<endl;
vector<int> tmp = range_query(l,r,1);
return tmp[0];
}
vector<int> range_query(int l,int r,int cur){
//cerr<<cur<<" "<<l<<" "<<r<<" "<<left[cur]<<" "<<right[cur]<<" ";
if(l >= right[cur] || r <= left[cur]){
//cerr<<"mimo"<<endl;
return {0,0,0};
}
if(l <= left[cur] && r >= right[cur]){
//cerr<<"cely in"<<endl;
return {vals[cur],l_vals[cur],r_vals[cur],vals[cur] == right[cur] - left[cur]};
}
//cerr<<"divne"<<endl;
return combine(range_query(l,r,cur*2),range_query(l,r,cur*2+1));
}
};
vector<ll> minimum_costs(vector<int> H,vector<int> L,vector<int> R){
int q = L.size(),n = H.size();
if(0 && n <= 3000 && q <= 10){
vector<ll> anss;
for(int Q = 0;Q<q;Q++){
ll ans = 1e16;
for(int i = L[Q];i<=R[Q];i++){
ll tmp = H[i];
ll mx = H[i];
for(int j = i+1;j <= R[Q];j++){
mx = max(mx,(ll)H[j]);
tmp += mx;
}
mx = H[i];
for(int j = i-1;j >= L[Q];j--){
mx = max(mx,(ll)H[j]);
tmp += mx;
}
ans = min(ans,tmp);
}
anss.push_back(ans);
}
return anss;
}
vector<int> tmp;
for(auto i : H) tmp.push_back(i == 1 ? 1 : 0);
Tree tr(n,tmp);
//for(int i = 1;i < 2*tr.n;i++)cerr<<i<<" "<<tr.vals[i]<<" "<<tr.l_vals[i]<<" "<<tr.r_vals[i]<<endl;
vector<ll> ans;
for(int i = 0;i<q;i++){
//cerr<<L[i]<<" "<<R[i]<<endl;
//cerr<<"xd "<<tr.range_query(L[i],R[i]+1)<<endl;
ans.push_back(2*(R[i] - L[i] + 1) - tr.range_query(L[i],R[i]+1));
}
return ans;
}
