#include "towers.h"

#include <vector>
#include <algorithm>
#include <iostream>
#include <stack>
//#include <cassert>

int mx[20][100005], mn[20][100005], a[100005];
int mni(int x, int y) { return a[x] < a[y] ? x : y; }
int mxi(int x, int y) { return a[x] < a[y] ? y : x; }

int getmx(int L, int R) {
	int t = __builtin_log2(R - L + 1);
	int x = mx[t][L], y = mx[t][R - (1 << t) + 1];
	return mxi(x, y);
}
int getmn(int L, int R) {
	int t = __builtin_log2(R - L + 1);
	int x = mn[t][L], y = mn[t][R - (1 << t) + 1];
	return mni(x, y);
}

int root[100005], A[8000006], ls[8000006], rs[8000006];
int tl[100005], tr[100005], tot, n, cls[100005], crs[100005];
int dfs(int l, int r, int p) {
	if (l > r) return 0;
	int u = getmx(l, r);
	int ls = cls[u] = dfs(l, u - 1, a[u]), rs = crs[u] = dfs(u + 1, r, a[u]);
	tr[u] = p - a[getmn(l, r)];
	tl[u] = std::max(tr[ls], tr[rs]) + 1;
	return u;
}
int clone(int u) {
	tot++, ls[tot] = ls[u], rs[tot] = rs[u], A[tot] = A[u];
	return tot;
}
void insert(int &u, int l, int r, int k, int d) {
	u = clone(u);
	if (l == r) return A[u] += d, void();
	int mid = (l + r) >> 1;
	if (k <= mid) insert(ls[u], l, mid, k, d);
	else insert(rs[u], mid + 1, r, k, d);
	A[u] = A[ls[u]] + A[rs[u]];
}
int sum(int u, int l, int r, int L, int R) {
	if (!u) return 0;
	if (l >= L && r <= R) return A[u];
	if (r < L || l > R) return 0;
	int mid = (l + r) >> 1;
	return sum(ls[u], l, mid, L, R) + sum(rs[u], mid + 1, r, L, R);
}

struct segtree {
	int a[100005], root[100005], tot, b[100005], rootb[100005], tl[100005], tr[100005];
	int A[16000006], ls[16000006], rs[16000006], B[16000006];
	int clone(int u) {
		tot++, ls[tot] = ls[u], rs[tot] = rs[u], A[tot] = A[u], B[tot] = B[u];
		return tot;
	}
	void modify(int &u, int l, int r, int k, int d) {
		u = clone(u);
		if (l == r) return A[u] = d, void();
		int mid = (l + r) >> 1;
		if (k <= mid) modify(ls[u], l, mid, k, d);
		else modify(rs[u], mid + 1, r, k, d);
		A[u] = std::max(A[ls[u]], A[rs[u]]);
	}
	void modifyB(int &u, int l, int r, int k, int d) {
		if (k > r || k < l) return;
		u = clone(u);
		if (l == r) return B[u] += d, void();
		int mid = (l + r) >> 1;
		if (k <= mid) modifyB(ls[u], l, mid, k, d);
		else modifyB(rs[u], mid + 1, r, k, d);
		B[u] = B[ls[u]] + B[rs[u]];
	}
	int ask(int u, int l, int r, int L, int R, int D) {
		if (!u) return 0;
		if (r < L || l > R) return 0;
		if (!A[u]) return 0;
		if (A[u] < D) return 0;
		if (l == r) return l;
		int mid = (l + r) >> 1, tl = ask(ls[u], l, mid, L, R, D);
		if (tl) return tl;
		else return ask(rs[u], mid + 1, r, L, R, D);
	}
	int sum(int u, int l, int r, int L, int R) {
		if (!u) return 0;
		if (l >= L && r <= R) return B[u];
		if (r < L || l > R) return 0;
		int mid = (l + r) >> 1;
		return sum(ls[u], l, mid, L, R) + sum(rs[u], mid + 1, r, L, R);
	}
	void build(int N) {
		static std::stack<int> sta;
		a[N + 1] = 2e9, sta.push(N + 1);
		for (int i = N; i >= 1; i--) {
			root[i] = root[i + 1], rootb[i] = rootb[i + 1];
			while (a[sta.top()] < a[i]) {
				modify(root[i], 1, N, sta.top(), 0);
				modifyB(rootb[i], 0, 1e9, tl[sta.top()], -1);
				modifyB(rootb[i], 0, 1e9, tr[sta.top()] + 1, 1);
			   	sta.pop();
			}
			modifyB(rootb[i], 0, 1e9, tl[i], 1);
			modifyB(rootb[i], 0, 1e9, tr[i] + 1, -1);
			modify(root[i], 1, N, i, b[i]);
		   	sta.push(i);
		}
	}
} B, C;

void init(int N, std::vector<int> H) {
	n = N;
    for (int i = 1; i <= N; i++) mx[0][i] = i, mn[0][i] = i, a[i] = H[i - 1];
    for (int i = 1; i <= __builtin_log2(N); i++) {
        for (int j = 1; j + (1 << i) <= N + 1; j++) {
            mx[i][j] = mxi(mx[i - 1][j], mx[i - 1][j + (1 << (i - 1))]);
            mn[i][j] = mni(mn[i - 1][j], mn[i - 1][j + (1 << (i - 1))]);
        }
    }
	dfs(1, N, 1e9 + a[getmn(1, N)]);
	for (int i = 1; i <= N; i++) {
		root[i] = root[i - 1];
		if (tl[i] > tr[i]) continue;
		insert(root[i], 0, 1e9, tl[i], 1);
		if (tr[i] < 1e9) insert(root[i], 0, 1e9, tr[i] + 1, -1);
	}
	for (int i = 1; i <= N; i++) {
		B.a[i] = a[i], B.b[i] = tr[crs[i]];
		B.tl[i] = tl[i], B.tr[i] = tr[i];
	   	C.a[i] = a[N - i + 1], C.b[i] = tr[cls[N - i + 1]];
		C.tl[i] = tl[N - i + 1], C.tr[i] = tr[N - i + 1];
	}
	B.build(N), C.build(N);
}

int max_towers(int L, int R, int D) {
	L++, R++;
//	for (int i = L; i < R; i++) if (a[i] > a[i + 1]) return -1;
	int ans = sum(root[R], 0, 1e9, 0, D) - sum(root[L - 1], 0, 1e9, 0, D);
	int u = getmx(L, R);
	int l = B.ask(B.root[L], 1, n, L, n, D), r = n - C.ask(C.root[n - R + 1], 1, n, n - R + 1, n, D) + 1;
	if (!l || l > u) l = u;
	if (r > n || r < u) r = u;
//	std::cerr << l << " " << r << " " << u << std::endl;
//	std::cerr << L << " " << R << " " << D << std::endl;
//	std::cerr << ans << std::endl;
//	std::cerr << D << " " << tr[getmx(L, R)] << " " << tl[getmx(L, R)] << std::endl;
	if (l != L) {
//		int _ = B.sum(B.rootb[L], 0, 1e9, 0, D);
		int t = getmx(L, l - 1);
//		assert(0 <= _ && _ <= 1);
		if (D <= tr[t] && B.sum(B.rootb[L], 0, 1e9, 0, D)) ans--;
		if (a[getmn(L, l - 1)] <= a[l] - D) ans++;
	}
	if (r != R) {
//		int _ = C.sum(C.rootb[n - R + 1], 0, 1e9, 0, D);
		int t = getmx(r + 1, R);
//		assert(0 <= _ && _ <= 1);
		if (D <= tr[t] && C.sum(C.rootb[n - R + 1], 0, 1e9, 0, D)) ans--;
		if (a[getmn(r + 1, R)] <= a[r] - D) ans++;
	}
//	assert(ans >= 0);
	return ans ? ans : 1;
}