#include "towers.h"

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

using namespace std;

namespace {

const int N = 1e5 + 7;
const int L = 18;
const int T = 5e6 + 7;

int n;
int h[N];
int prv[N], nxt[N];
int stmx[L][N];
int dprv[N], dnxt[N];
int d1[N];
vector<int> xs;
vector<int> gprv[N], gnxt[N];
int rootpref[N], rootprv[N], rootnxt[N];
int emp, sz;
int vsum[T], vl[T], vr[T];
int vcnt = 1;

int copy(int v) {
	int u = vcnt++; 
	vsum[u] = vsum[v];
	vl[u] = vl[v];
	vr[u] = vr[v];
	return u;
}

int upd(int v, int tl, int tr, int ind, int val) {
	v = copy(v);
	if (tr - tl == 1) {
		vsum[v] += val;
		return v;
	} 
	int tm = (tl + tr) / 2;
	if (ind < tm) {
		vl[v] = upd(vl[v], tl, tm, ind, val);
	} else {
		vr[v] = upd(vr[v], tm, tr, ind, val);
	}
	vsum[v] = vsum[vl[v]] + vsum[vr[v]];
	return v;
}

int getsum(int v, int tl, int tr, int l, int r) {
	if (tl >= r || tr <= l) {
		return 0;
	}
	if (tl >= l && tr <= r) {
		return vsum[v];
	}
	int tm = (tl + tr) / 2;
	return getsum(vl[v], tl, tm, l, r) + getsum(vr[v], tm, tr, l, r);
}

int build(int tl, int tr) {
	int v = copy(0);
	if (tr - tl != 1) {
		int tm = (tl + tr) / 2;
		vl[v] = build(tl, tm);
		vr[v] = build(tm, tr);
	}
	return v;
}

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]);
		}
	}
	for (int i = 0; i < n; ++i) {
		dprv[i] = getmx(prv[i] + 1, i + 1) - h[i];
		dnxt[i] = getmx(i, nxt[i]) - h[i];
		d1[i] = min(dprv[i], dnxt[i]);
		xs.push_back(dprv[i]);
		xs.push_back(dnxt[i]);
		if (prv[i] != -1) {
			gprv[prv[i]].push_back(i);
		}
		if (nxt[i] != n) {
			gnxt[nxt[i]].push_back(i);
		}
	}
	xs.push_back(1e9 + 1);
	sort(xs.begin(), xs.end());
	xs.resize(unique(xs.begin(), xs.end()) - xs.begin());
	sz = xs.size();
	for (int i = 0; i < n; ++i) {
		dprv[i] = lower_bound(xs.begin(), xs.end(), dprv[i]) - xs.begin();
		dnxt[i] = lower_bound(xs.begin(), xs.end(), dnxt[i]) - xs.begin();
		d1[i] = lower_bound(xs.begin(), xs.end(), d1[i]) - xs.begin();
	}
	emp = build(0, sz);
	rootpref[0] = emp;
	for (int i = 0; i < n; ++i) {
		rootpref[i + 1] = upd(rootpref[i], 0, sz, d1[i], 1);
	}
	for (int i = 0; i < n; ++i) {
		if (prv[i] == -1) {
			rootprv[i] = emp;
		} else {
			rootprv[i] = rootprv[prv[i]];
		}
		if (d1[i] < dprv[i]) {
			rootprv[i] = upd(rootprv[i], 0, sz, d1[i] + 1, 1);
			rootprv[i] = upd(rootprv[i], 0, sz, dprv[i] + 1, -1);
		}
	}
	for (int i = n - 1; i >= 0; --i) {
		if (nxt[i] == -1) {
			rootnxt[i] = emp;
		} else {
			rootnxt[i] = rootnxt[nxt[i]];
		}
		if (d1[i] < dnxt[i]) {
			rootnxt[i] = upd(rootnxt[i], 0, sz, d1[i] + 1, 1);
			rootnxt[i] = upd(rootnxt[i], 0, sz, dnxt[i] + 1, -1);
		}
	}
}

int max_towers(int grdl, int grdr, int grdd) {
	int l = grdl;
	int r = grdr;
	int d = grdd;
	d = lower_bound(xs.begin(), xs.end(), d) - xs.begin(); 
	++r;
	int ret = getsum(rootpref[r], 0, sz, d, sz) - getsum(rootpref[l], 0, sz, d, sz);
	{
		ret += getsum(rootnxt[l], 0, sz, 0, d);
		int ind = l;
		while (nxt[ind] < r) {
			ind = nxt[ind];
		}
		if (d1[ind] < d) {
			++ret;
		}
		ret -= getsum(rootnxt[ind], 0, sz, 0, d);
	}
	{
		ret += getsum(rootprv[r - 1], 0, sz, 0, d);
		int ind = r - 1;
		while (prv[ind] >= l) {
			ind = prv[ind];
		}
		ret -= getsum(rootprv[ind], 0, sz, 0, d);
	}
	return ret;
}