//#include "towers.h"
#include <vector>
#include <iostream>
typedef std::vector<int> vi;
typedef std::vector<vi> vvi;
std::vector<int> real_h(0);
vvi maxi(0);
int total_maxi = 0;
bool is_interesting = false;
void init_maxi(int N) {
maxi.resize(N, vi(0));
for (int i = 0; i < N; i++) {
maxi[i].push_back(i);
}
int size = 2;
while (size <= N) {
for (int i = 0; i < N; i += size) {
int value = maxi[i][maxi[i].size() - 1];
int next_place = i + (size / 2);
if (next_place < N) {
int other_value = maxi[next_place][maxi[next_place].size() - 1];
if (real_h[other_value] > real_h[value]) {
value = other_value;
}
}
maxi[i].push_back(value);
}
size *= 2;
}
}
void init_is_interesting(int N) {
bool going_up = true;
for (int i = 1; i < N; i++) {
if (real_h[i] < real_h[i - 1]) {
if (going_up) {
going_up = false;
}
else {
return;
}
}
else {
if (!going_up) {
return;
}
}
}
is_interesting = true;
}
void init(int N, std::vector<int> H) {
real_h.resize(N);
for (int i = 0; i < N; i++) {
real_h[i] = H[i];
if (real_h[i] > total_maxi) {
total_maxi = real_h[i];
}
}
init_maxi(N);
}
int get_max_id2(int l, int r) {
if (l == r) {
return l;
}
int size = 1;
for (int i = 1; i < maxi[l].size(); i++) {
if (l + size + size - 1 > r) {
int temp_maxi = maxi[l][i - 1];
if (l + size - 1 == r) {
return temp_maxi;
}
else {
int other_res = get_max_id2(l + size, r);
if (real_h[other_res] > real_h[temp_maxi]) {
return other_res;
}
return temp_maxi;
}
}
size *= 2;
}
int temp_maxi = maxi[l][maxi[l].size() - 1];
if (l + size - 1 == r) {
return temp_maxi;
}
else {
int other_res = get_max_id2(l + size, r);
if (real_h[other_res] > real_h[temp_maxi]) {
return other_res;
}
return temp_maxi;
}
}
int get_max_id(int l, int r) {
int max_result = real_h[l];
int max_id =l;
for (int i = l + 1; i <= r; i++) {
if (real_h[i] > max_result) {
max_result = real_h[i];
max_id = i;
}
}
return max_id;
}
int get_min_id(int l, int r) {
int min_result= real_h[l];
int min_id =l;
for (int i = l + 1; i <= r; i++) {
if (real_h[i] < min_result) {
min_result = real_h[i];
min_id = i;
}
}
return min_id;
}
int max_towers_interesting(int l, int r, int d) {
int max_id = get_max_id2(l, r);
if (l == r) {
return 1;
}
if (real_h[max_id] != total_maxi) {
return 1;
}
if (max_id == l) {
return 1;
}
if (max_id == r) {
return 1;
}
return 2;
}
int max_towers2(int l, int r, int d, int max_possible_value) {
if (l > r) {
return 0;
}
if (l == r) {
if (real_h[l] <= max_possible_value) {
return 1;
}
return 0;
}
if (l + 1 == r) {
if (real_h[l] <= max_possible_value || real_h[l + 1] <= max_possible_value) {
return 1;
}
return 0;
}
int max_id = get_max_id2(l, r);
int left_value = max_towers2(l, max_id - 1, d, real_h[max_id] - d);
int right_value = max_towers2(max_id + 1, r, d, real_h[max_id] - d);
if (left_value + right_value == 0) {
int min_id = get_min_id(l, r);
if (real_h[min_id] <= max_possible_value) {
return 1;
}
}
return left_value + right_value;
}
int max_towers(int L, int R, int D) {
if (is_interesting) {
return max_towers_interesting(L, R, D);
}
return max_towers2(L, R, D, total_maxi);
}
/*int main() {
init(7, std::vector<int>{10, 20, 60, 40, 50, 30, 70});
std::cout << max_towers(1, 5, 10) << std::endl;
std::cout << max_towers(2, 2, 100) << std::endl;
std::cout << max_towers(0, 6, 17) << std::endl;
}//*/
