#include "towers.h"
#include <vector>
#include <iostream>
std::vector<int> real_h(0);
int maxi = 0;
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] > maxi) {
maxi = real_h[i];
}
}
}
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_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_id(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) {
return max_towers2(L, R, D, 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;
}*/
