#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int maxn = 1e5 + 5;
const int inf = 1e9;

int a[maxn], n;
int stk[maxn], tp;
int L[maxn], R[maxn], d[maxn];
int nxt[18][maxn], pre[18][maxn];

struct ST
{
    int mi[18], lg[maxn];
    int f[18][maxn];

    void build()
    {
        for (int i = 0; i <= 17; i++) mi[i] = 1 << i;
        for (int i = 1, k = 0; i <= n; i++)
        {
            lg[i] = k; if (i == (1 << (k + 1))) lg[i] = ++k;
            f[0][i] = a[i];
        }
        for (int j = 1; j <= 17; j++)
            for (int i = 1; i + mi[j] - 1 <= n; i++)
                f[j][i] = max(f[j - 1][i], f[j - 1][i + mi[j - 1]]);
    }

    int query(int l, int r)
    {
        if (l > r) return 0;
        int k = lg[r - l + 1];
        return max(f[k][l], f[k][r - mi[k] + 1]);
    }
}st;

int rt[maxn], sum[maxn * 35], ls[maxn * 35], rs[maxn * 35], cnt;
void update(int &k, int p, int l, int r, int x)
{
    k = ++cnt;
    sum[k] = sum[p] + 1, ls[k] = ls[p], rs[k] = rs[p];
    if (l == r) return;
    int mid = (l + r) >> 1;
    if (x <= mid) update(ls[k], ls[p], l, mid, x);
    else update(rs[k], rs[p], mid + 1, r, x);
}
int ask(int k, int l, int r, int x)
{
    if (!k) return 0;
    if (l == r) return sum[k];
    int mid = (l + r) >> 1;
    if (x > mid) return ask(rs[k], mid + 1, r, x);
    else return ask(ls[k], l, mid, x) + sum[rs[k]];
}

void init(int N, vector<int> H)
{
    n = N;
    for (int i = 1; i <= N; i++) a[i] = H[i - 1]; st.build();

    tp = 0;
    for (int i = 1; i <= N; i++)
    {
        while (tp && a[stk[tp]] > a[i]) tp--;
        L[i] = tp ? stk[tp] + 1 : 1;
        stk[++tp] = i;
    }

    tp = 0;
    for (int i = N; i; i--)
    {
        while (tp && a[stk[tp]] > a[i]) tp--;
        R[i] = tp ? stk[tp] - 1 : n;
        d[i] = min(st.query(L[i], i - 1), st.query(i + 1, R[i])) - a[i];
        stk[++tp] = i;
    }

    for (int i = 1; i <= N; i++)
        if (d[i] > 0) update(rt[i], rt[i - 1], 1, inf, d[i]); else rt[i] = rt[i - 1];

    for (int i = 1; i <= N; i++) nxt[0][i] = R[i] + 1; nxt[0][N + 1] = N + 1;
    for (int j = 1; j <= 17; j++)
        for (int i = 1; i <= N + 1; i++) nxt[j][i] = nxt[j - 1][nxt[j - 1][i]];
    for (int i = 1; i <= N; i++) pre[0][i] = L[i] - 1;
    for (int j = 1; j <= 17; j++)
        for (int i = 1; i <= N; i++) pre[j][i] = pre[j - 1][pre[j - 1][i]];
}

int max_towers(int l, int r, int D)
{
    l++, r++;
    int ans = ask(rt[r], 1, inf, D) - ask(rt[l - 1], 1, inf, D);
    int x1 = l;
    for (int i = 17; ~i; i--)
        if (nxt[i][x1] <= r && L[nxt[i][x1]] < l) x1 = nxt[i][x1];
    if (d[x1] < D && st.query(x1 + 1, R[x1]) - a[x1] >= D) ans++;
    int x2 = r;
    for (int i = 17; ~i; i--)
        if (pre[i][x2] >= l && R[pre[i][x2]] > r) x2 = pre[i][x2];
    if (x2 != x1 && d[x2] < D && st.query(L[x2], x2 - 1) - a[x2] >= D) ans++;
    return max(1, ans);
}