#include "towers.h"

#include <vector>
#include <bits/stdc++.h>

using namespace std;

namespace {

const int N = 1e5 + 7;
const int L = 18;

int n;
int h[N];
int prv[N], nxt[N];
int stmx[L][N];

int getmx(int l, int r) {
	int t = 31 - __builtin_clz(r - l);
	return max(stmx[t][l], stmx[t][r - (1 << t)]);
}

}

void init(int grdn, vector<int> grdh) {
	n = grdn;
	for (int i = 0; i < n; ++i) {
		h[i] = grdh[i];
	}
	{
		for (int i = 0; i < n; ++i) {
			nxt[i] = n;
		}
		vector<int> st;
		for (int i = 0; i < n; ++i) {
			while (!st.empty() && h[st.back()] > h[i]) {
				nxt[st.back()] = i;
				st.pop_back();
			}
			st.push_back(i);
		}
	}
	{
		for (int i = 0; i < n; ++i) {
			prv[i] = -1;
		}
		vector<int> st;
		for (int i = n - 1; i >= 0; --i) {
			while (!st.empty() && h[st.back()] > h[i]) {
				prv[st.back()] = i;
				st.pop_back();
			}
			st.push_back(i);
		}
	}
	for (int i = 0; i < n; ++i) {
		stmx[0][i] = h[i];
	}
	for (int t = 1; t < L; ++t) {
		int pw = 1 << t;
		for (int i = 0; i + pw <= n; ++i) {
			stmx[t][i] = max(stmx[t - 1][i], stmx[t - 1][i + pw / 2]);
		}
	}
}

int max_towers(int grdl, int grdr, int grdd) {
	int l = grdl;
	int r = grdr;
	int d = grdd;
	++r;
	int ret = 0;
	for (int i = l; i < r; ++i) {
		bool ok = 1;
		if (prv[i] >= l) {
			ok &= getmx(prv[i] + 1, i + 1) >= h[i] + d;
		}
		if (nxt[i] < r) {
			ok &= getmx(i, nxt[i]) >= h[i] + d;
		}
		if (ok) {
			++ret;
		}
	}
	return ret;
}