#include <bits/stdc++.h>
#define MAX 100010
using namespace std;
typedef long long int lli;
class SegmentTree
{
public:
int getLeft(int node) { return 2*node; }
int getRight(int node) { return 2*node + 1; }
void merge(int node, int idLeft, int idRight)
{
mx[ node ] = max(mx[ idLeft ] , mx[ idRight ]);
blockLeft[ node ] = blockLeft[ idLeft ];
blockRight[ node ] = blockRight[ idRight ];
if(mx[ idLeft ] == 1) blockLeft[ node ] += blockLeft[ idRight ];
if(mx[ idRight ] == 1) blockRight[ node ] += blockRight[ idLeft ];
block[ node ] = max(block[ idLeft ] , block[ idRight ]);
block[ node ] = max(block[ node ] , blockRight[ idLeft ] + blockLeft[ idRight ]);
}
void build(int node, int l, int r, int* v)
{
N = max(N , r);
if(l == r)
{
int aux = 0;
if(v[l] == 1) aux = 1;
mx[ node ] = v[ l ];
block[ node ] = aux;
blockLeft[ node ] = aux;
blockRight[ node ] = aux;
return;
}
int m = (l + r)/2;
build(getLeft(node) , l , m , v);
build(getRight(node) , m + 1 , r , v);
merge(node , getLeft(node) , getRight(node));
}
void query(int node, int l, int r, int i, int j)
{
if(j < l || r < i) return;
if(i <= l && r <= j)
{
merge(1 , 0 , node);
mx[0] = mx[1];
block[0] = block[1];
blockLeft[0] = blockLeft[1];
blockRight[0] = blockRight[1];
return;
}
int m = (l + r)/2;
query(getLeft(node) , l , m , i , j);
query(getRight(node) , m + 1 , r , i , j);
}
int query(int l, int r)
{
mx[0] = mx[1] = -1;
block[0] = block[1] = 0;
blockLeft[0] = blockLeft[1] = 0;
blockRight[0] = blockRight[0] = 0;
query(2 , 1 , N , l , r);
return block[ 0 ];
}
SegmentTree() : N( 0 ) {}
private:
int N;
int mx[4*MAX];
int block[4*MAX];
int blockLeft[4*MAX];
int blockRight[4*MAX];
};
int N, Q;
int v[MAX];
vector<lli> ans;
SegmentTree SEG;
vector<long long int> minimum_costs(vector<int> H, vector<int> l, vector<int> r)
{
N = H.size(); Q = l.size();
for(int g = 1 ; g <= N ; g++)
v[ g ] = H[ g - 1 ];
SEG.build(1 , 1 , N , v);
for(int g = 0 ; g < Q ; g++)
{
int L = l[g] + 1;
int R = r[g] + 1;
int blockOne = SEG.query(L , R);
ans.push_back( blockOne*1 + (R - L + 1 - blockOne)*2 );
}
return ans;
}
/*int main()
{
int nn, qq;
scanf("%d %d",&nn,&qq);
vector<int> hh(nn);
vector<int> ll(qq), rr(qq);
for(int g = 0 ; g < nn ; g++)
scanf("%d",&hh[g]);
for(int g = 0 ; g < qq ; g++)
scanf("%d %d",&ll[g],&rr[g]);
vector<lli> aux = minimum_costs(hh , ll , rr);
for(int g = 0 ; g < qq ; g++)
printf("%lld\n",aux[g]);
}*/
