#include "towers.h"
#include <bits/stdc++.h>
using namespace std;
int n;
vector<int> arr;
int sort_index[101010];
struct maxseg {
int tree[404040];
vector<int> initarr;
void init(int v, int st, int ed) {
if (st == ed) {
tree[v] = initarr[st];
return;
}
int mid = (st + ed) / 2;
init(2 * v, st, mid);
init(2 * v + 1, mid + 1, ed);
tree[v] = max(tree[2 * v], tree[2 * v + 1]);
}
void update(int v, int st, int ed, int idx, int val) {
if (idx < st || idx > ed) return;
if (idx == st && idx == ed) {
tree[v] = val;
return;
}
int mid = (st + ed) / 2;
update(2 * v, st, mid, idx, val);
update(2 * v + 1, mid + 1, ed, idx, val);
tree[v] = max(tree[2 * v], tree[2 * v + 1]);
}
int get(int v, int st, int ed, int gs, int ge) {
if (st > ge || ed < gs) return -1;
if (gs <= st && ed <= ge) return tree[v];
int mid = (st + ed) / 2;
return max(get(2 * v, st, mid, gs, ge), get(2 * v + 1, mid + 1, ed, gs, ge));
}
} max_value, left_index;
struct minseg {
int tree[404040];
vector<int> initarr;
void init(int v, int st, int ed) {
if (st == ed) {
tree[v] = initarr[st];
return;
}
int mid = (st + ed) / 2;
init(2 * v, st, mid);
init(2 * v + 1, mid + 1, ed);
tree[v] = min(tree[2 * v], tree[2 * v + 1]);
}
void update(int v, int st, int ed, int idx, int val) {
if (idx < st || idx > ed) return;
if (idx == st && idx == ed) {
tree[v] = val;
return;
}
int mid = (st + ed) / 2;
update(2 * v, st, mid, idx, val);
update(2 * v + 1, mid + 1, ed, idx, val);
tree[v] = min(tree[2 * v], tree[2 * v + 1]);
}
int get(int v, int st, int ed, int gs, int ge) {
if (st > ge || ed < gs) return n;
if (gs <= st && ed <= ge) return tree[v];
int mid = (st + ed) / 2;
return min(get(2 * v, st, mid, gs, ge), get(2 * v + 1, mid + 1, ed, gs, ge));
}
} right_index;
void init(int N, vector<int> H) {
n = N;
vector< pair<int, int> > temp;
for (int i = 0; i < N; i++) arr.push_back(H[i]);
for (int i = 0; i < N; i++) temp.push_back({H[i], i});
sort(temp.begin(), temp.end());
for (int i = 0; i < N; i++) {
sort_index[i] = temp[i].second;
}
max_value.initarr = arr;
right_index.initarr = vector<int>(n, n);
left_index.initarr = vector<int>(n, -1);
max_value.init(1, 0, n - 1);
}
int max_towers(int L, int R, int D) {
int ans = 0;
left_index.init(1, 0, n - 1);
right_index.init(1, 0, n - 1);
for (int i = 0; i < n; i++) {
if (sort_index[i] < L || sort_index[i] > R) continue;
bool f = true;
int j = right_index.get(1, 0, n - 1, sort_index[i] + 1, R);
//cout << sort_index[i] << " " << j << "\n";
if (j >= 0 && j < n)
if (max_value.get(1, 0, n - 1, sort_index[i] + 1, j - 1) < max(arr[sort_index[i]], arr[j]) + D)
f = false;
j = left_index.get(1, 0, n - 1, L, sort_index[i] - 1);
//cout << j << " " << sort_index[i] << "\n";
if (j >= 0 && j < n)
if (max_value.get(1, 0, n - 1, j + 1, sort_index[i] - 1) < max(arr[sort_index[i]], arr[j]) + D)
f = false;
if (f) {
ans++;
left_index.update(1, 0, n - 1, sort_index[i], sort_index[i]);
right_index.update(1, 0, n - 1, sort_index[i], sort_index[i]);
}
}
return ans;
}
