#include "towers.h"
#include <vector>
#include <algorithm>
#include <numeric>
#include <iostream>
namespace ruhan {
using namespace std;
int N;
vector<int> H;
vector<int> max_rmq[20];
vector<int> min_rmq[20];
int good_pos = -1;
vector<int> lg;
int my_max (int x, int y) {
return H[x] > H[y] ? x : y;
}
int my_min (int x, int y) {
return H[x] < H[y] ? x : y;
}
template<class F>
void rmq_init (vector<int> *rmq, F func) {
rmq[0].resize(N);
iota(rmq[0].begin(), rmq[0].end(), 0);
for (int k = 0; k < 19; k++) {
rmq[k+1].resize(N);
for (int i = 0; i < N; i++) {
if (i + (1 << k) < N) rmq[k+1][i] = func(rmq[k][i], rmq[k][i+(1<<k)]);
else rmq[k+1][i] = rmq[k][i];
}
}
}
template<class F>
int rmq_get (vector<int> *rmq, F func, int l, int r) {
int k = lg[r - l + 1];
return func(rmq[k][l], rmq[k][r - (1 << k) + 1]);
}
void init (int N_, vector<int> H_) {
N = N_; H = H_;
for (int i = 0; i < N; i++) {
if ((i == 0 || H[i-1] < H[i]) && (i == N - 1 || H[i+1] > H[i])) {
if (good_pos == -1) good_pos = i;
else good_pos = -2;
}
}
rmq_init(max_rmq, my_max);
rmq_init(min_rmq, my_min);
lg.resize(N + 1);
lg[1] = 0;
for (int x = 2; x <= N; x++) {
lg[x] = lg[x/2] + 1;
}
//cerr << "init done\n";
}
int calc (int L, int R, int D, int mx) {
if (good_pos >= 0) {
if (good_pos <= L && good_pos >= R) return 1;
int x = rmq_get(min_rmq, my_min, L, good_pos - 1);
int y = rmq_get(min_rmq, my_min, good_pos + 1, R);
if (H[x] + D <= H[good_pos] && H[y] + D <= H[good_pos]) return 2;
else return 1;
}
if (L > R) return 0;
if (L == R) return H[L] <= mx;
//cerr << L << " " << R << " " << D << " " << mx << ", ";
int xi = rmq_get(min_rmq, my_min, L, R);
int yi = rmq_get(max_rmq, my_max, L, R);
//cerr << "xi = " << xi << ", yi = " << yi << "\n";
if (H[xi] > mx) return 0;
return max(1, calc(L, yi - 1, D, H[yi] - D) + calc(yi + 1, R, D, H[yi] - D));
}
};
void init(int N, std::vector<int> H) {
ruhan::init(N, H);
}
int max_towers(int L, int R, int D) {
return ruhan::calc(L, R, D, int(2e9));
}
