#include <bits/stdc++.h>
#include "towers.h"
using namespace std;
const int N = 1e5 + 10 , inf = 1e9 , Lg = 17;
int n , a[N] , rmxq[N][Lg] , rmnq[N][Lg] , lg2[N];
int b[N] , psum[N];
int mn_pos(int aa , int bb)
{
if(a[aa] < a[bb])
return aa;
return bb;
}
int mx_pos(int aa , int bb)
{
if(a[aa] > a[bb])
return aa;
return bb;
}
void Build()
{
lg2[1] = 0;
for(int i = 2 ; i < N ; i++)
lg2[i] = lg2[i / 2] + 1;
for(int i = 0 ; i < n ; i++)
rmnq[i][0] = rmxq[i][0] = i;
for(int j = 1 ; j < Lg ; j++)
{
int len = (1 << j);
for(int i = 0 ; i + len <= n ; i++)
{
rmnq[i][j] = mn_pos(rmnq[i][j - 1] , rmnq[i + len / 2][j - 1]);
rmxq[i][j] = mx_pos(rmxq[i][j - 1] , rmxq[i + len / 2][j - 1]);
}
}
for(int i = 1 ; i + 1 < n ; i++) if(a[i] > a[i - 1] && a[i] > a[i + 1])
b[i] = 1;
for(int i = 1 ; i < n ; i++)
psum[i] = psum[i - 1] + b[i];
}
int Get_mx(int l , int r)
{
r++;
int sz = (r - l); sz = lg2[sz];
return mx_pos(rmxq[l][sz] , rmxq[r - (1 << sz)][sz]);
}
int Get_mn(int l , int r)
{
r++;
int sz = (r - l); sz = lg2[sz];
return mn_pos(rmnq[l][sz] , rmnq[r - (1 << sz)][sz]);
}
void init(int nn , vector <int> vec)
{
n = nn;
for(int i = 0 ; i < n ; i++)
a[i] = vec[i];
Build();
}
int Solve(int l , int r , int d , int val)
{
if(l > r)
return 0;
int mn = a[Get_mn(l , r)];
int pos_mx = Get_mx(l , r);
if(mn > val)
return 0;
int res = max(1 , Solve(l , pos_mx - 1 , d , a[pos_mx] - d) + Solve(pos_mx + 1 , r , d , a[pos_mx] - d));
return res;
}
int max_towers(int l , int r , int d)
{
if(d == 1)
{
if(l + 1 >= r)
return 1;
return 1 + psum[r - 1] - psum[l];
}
if(psum[r - 1] - psum[l] == 0)
return 1;
if(psum[r - 1] - psum[l] == 1)
{
int id = Get_mx(l , r);
int lc = Get_mn(l , id - 1) , rc = Get_mn(id + 1 , r);
if(a[id] - d >= a[lc] && a[id] - d >= a[rc])
return 2;
return 1;
}
return Solve(l , r , d , inf);
}
