#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
struct item{
long long l,r,m;
};
struct segment_tree{
vector<vector<item>>st;
vector<vector<pair<long long,long long>>>range;
segment_tree(long long n,vector<int>a){
long long q = 0;
for(long long i = 1; ; i+=i){
if(i >= n){
st.assign(log2(i)+1,vector<item>());
range.assign(log2(i)+1,vector<pair<long long,long long>>());
long long q = i;
for(long long j = 0; j < st.size(); j++){
st[j].assign(q,{0,0,0});
range[j].assign(q,{0,0});
q/=2;
}
q = i;
break;
}
}
for(long long i = 0; i < st[0].size(); i++){
range[0][i].first = i;
range[0][i].second = i;
}
for(long long i = 0; i < n; i++){
st[0][i].l = (a[i]==1);
st[0][i].r = (a[i]==1);
st[0][i].m = (a[i]==1);
}
for(long long i = 1; i < st.size(); i++){
for(long long j = 0; j < st[i].size(); j++){
item node1 = st[i-1][j*2];
item node2 = st[i-1][j*2+1];
st[i][j].l = node1.l;
st[i][j].r = node2.r;
long long x = range[i-1][j*2].second-range[i-1][j*2].first+1;
long long x2 = range[i-1][j*2+1].second-range[i-1][j*2+1].first+1;
if(node1.l == x){
st[i][j].l = node1.l + node2.l;
}
if(node2.r == x2){
st[i][j].r = node1.r + node2.r;
}
st[i][j].m = max(node1.m,node2.m);
st[i][j].m = max(st[i][j].m,node1.r+node2.l);
st[i][j].m = max(st[i][j].m,st[i][j].l);
st[i][j].m = max(st[i][j].m,st[i][j].r);
range[i][j].first = range[i-1][j*2].first;
range[i][j].second = range[i-1][j*2+1].second;
}
}
}
long long findl(long long left,long long right,long long i,long long j){
if(i < 0) return 0;
long long l = range[i][j].first;
long long r = range[i][j].second;
if(l >= left && right >= r) return st[i][j].l;
else findl(left,right,i-1,j*2);
}
long long findr(long long left,long long right,long long i,long long j){
if(i < 0) return 0;
long long l = range[i][j].first;
long long r = range[i][j].second;
if(l >= left && right >= r) return st[i][j].r;
else findr(left,right,i-1,j*2+1);
}
long long find(long long left,long long right,long long i=-1,long long j=-1){
if(i == -1){
i = st.size()-1;
j = 0;
}
long long l = range[i][j].first;
long long r = range[i][j].second;
long long ans = findl(left,right,i-1,j*2+1)+findr(left,right,i-1,j*2);
if(l > right || r < left) return ans;
else if(l >= left && r <= right){
ans = max(ans,st[i][j].m);
return ans;
}
else{
ans = max(ans,max(find(left,right,i-1,j*2+1),find(left,right,i-1,j*2)));
return ans;
}
}
};
vector<long long> minimum_costs(vector<int> H, vector<int> L,vector<int> R) {
long long q = L.size();
long long n = H.size();
vector<long long> ans(q);
segment_tree st(n,H);
for(long long v = 0; v < q; v++){
long long l = L[v];
long long r = R[v];
ans[v] = (2*(r-l+1))-st.find(l,r);
}
return ans;
}
// int main(){
// long long n,m; cin >> n >> m;
// vector<int>a(n);
// vector<int>b(m),c(m);
// for(long long i = 0; i < n; i++) cin >> a[i];
// for(long long i = 0; i < m; i++) cin >> b[i] >> c[i];
// vector<long long>ans = minimum_costs(a,b,c);
// for(long long i = 0; i < ans.size(); i++) cout << ans[i] << ' ';
// }
