#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>
#include <stack>
typedef long long llong;
const int MAXLOG = 20 + 5;
const int MAXN = 100000 + 10;
const int INF = 1e9;
int n;
struct MST
{
std::vector <int> tree[4*MAXN];
void build(int l, int r, int node, int vals[])
{
if (l == r)
{
tree[node].push_back(vals[l]);
return;
}
int mid = (l + r) / 2;
build(l, mid, 2*node, vals);
build(mid + 1, r, 2*node + 1, vals);
tree[node].reserve(r - l + 1);
int lPtr = 0, rPtr = 0;
for (int i = l ; i <= r ; ++i)
{
if (lPtr == tree[2*node].size())
{
tree[node].push_back(tree[2*node + 1][rPtr++]);
continue;
}
if (rPtr == tree[2*node + 1].size())
{
tree[node].push_back(tree[2*node][lPtr++]);
continue;
}
if (tree[2*node][lPtr] < tree[2*node + 1][rPtr])
{
tree[node].push_back(tree[2*node][lPtr++]);
} else
{
tree[node].push_back(tree[2*node + 1][rPtr++]);
}
}
}
int binary(int node, int val)
{
int l = -1, r = tree[node].size(), mid;
while (l < r - 1)
{
mid = (l + r) / 2;
if (tree[node][mid] < val) l = mid;
else r = mid;
}
return r;
}
int query(int l, int r, int node, int queryL, int queryR, int queryVal)
{
if (queryL <= l && r <= queryR)
{
return binary(node, queryVal);
}
int res = 0;
int mid = (l + r) / 2;
if (queryL <= mid) res += query(l, mid, 2*node, queryL, queryR, queryVal);
if (mid + 1 <= queryR) res += query(mid + 1, r, 2*node + 1, queryL, queryR, queryVal);
return res;
}
void build(int vals[])
{
build(1, n, 1, vals);
}
int query(int l, int r, int val)
{
return query(1, n, 1, l, r, val);
}
};
MST left, right;
struct Sparse
{
int sparse[MAXLOG][MAXN];
int vals[MAXN];
int lg[MAXN];
int cmp(int x, int y)
{
if (vals[x] > vals[y]) return x;
return y;
}
void build(int _vals[])
{
for (int i = 1 ; i <= n ; ++i)
{
sparse[0][i] = i;
vals[i] = _vals[i];
}
for (int log = 1 ; (1 << log) <= n ; ++log)
{
for (int i = 1 ; i + (1 << log) - 1 <= n ; ++i)
{
sparse[log][i] = cmp(sparse[log - 1][i], sparse[log - 1][i + (1 << log - 1)]);
}
}
for (int i = 1 ; i <= n ; ++i)
{
lg[i] = lg[i - 1];
if ((1 << lg[i] + 1) < i)
{
lg[i]++;
}
}
}
int findMAX(int l, int r)
{
int log = lg[r - l + 1];
return vals[cmp(sparse[log][l], sparse[log][r - (1 << log) + 1])];
}
int findIDX(int l, int r)
{
int log = lg[r - l + 1];
return cmp(sparse[log][l], sparse[log][r - (1 << log) + 1]);
}
};
int a[MAXN];
int b[MAXN];
int c[MAXN];
int d[MAXN];
int h[MAXN];
Sparse sparse;
std::stack <int> st;
std::vector <int> v;
int isClimb = -1;
void init(int N, std::vector <int> H)
{
n = N;
for (int i = 1 ; i <= n ; ++i)
{
h[i] = H[i - 1];
}
sparse.build(h);
st.push(0);
for (int i = 1 ; i <= n ; ++i)
{
while (h[st.top()] > h[i])
{
st.pop();
}
a[i] = st.top();
st.push(i);
}
for (int i = 1 ; i <= n ; ++i)
{
if ((i == 1 || h[i - 1] < h[i]) && (i == n || h[i] > h[i + 1]))
{
isClimb = i;
break;
}
}
for (int i = 1 ; i < isClimb ; ++i)
{
if (h[i] > h[i + 1])
{
isClimb = -1;
break;
}
}
if (isClimb != -1)
{
for (int i = isClimb ; i < n ; ++i)
{
if (h[i] < h[i + 1])
{
isClimb = -1;
break;
}
}
}
while (!st.empty())
{
st.pop();
}
st.push(n + 1);
for (int i = n ; i >= 1 ; --i)
{
while (h[st.top()] > h[i])
{
st.pop();
}
c[i] = st.top();
st.push(i);
}
for (int i = 1 ; i <= n ; ++i)
{
if (a[i] == i - 1)
{
b[i] = 0;
} else
{
b[i] = sparse.findMAX(a[i] + 1, i - 1) - h[i];
}
if (c[i] == i + 1)
{
d[i] = 0;
} else
{
d[i] = sparse.findMAX(i + 1, c[i] - 1) - h[i];
}
}
for (int i = 1 ; i <= n ; ++i)
{
int curr = INF;
if (a[i] > 0) curr = std::min(curr, b[i]);
if (c[i] < n + 1) curr = std::min(curr, d[i]);
v.push_back(curr);
}
std::sort(v.begin(), v.end());
}
bool entered;
int vals[MAXN];
int prefix[MAXN];
int max_towers(int L, int R, int D)
{
L++; R++;
if (isClimb != -1)
{
if (isClimb < L || R < isClimb)
{
return 1;
}
if (h[L] + D <= h[isClimb] && h[R] + D <= h[isClimb])
{
return 2;
}
return 1;
}
if (L == R)
{
return 1;
}
if (L == 1 && R == n)
{
int l = -1, r = n, mid;
while (l < r - 1)
{
mid = (l + r) / 2;
if (v[mid] < D) l = mid;
else r = mid;
}
return n - r;
}
if (!entered)
{
entered = true;
for (int i = 1 ; i <= n ; ++i)
{
if ((a[i] > 0 && b[i] < D) && (c[i] == n + 1 || d[i] >= D))
{
vals[i] = a[i];
} else
{
vals[i] = INF;
}
}
left.build(vals);
for (int i = 1 ; i <= n ; ++i)
{
if ((c[i] <= n && d[i] < D) && (a[i] == 0 || b[i] >= D))
{
vals[i] = c[i];
} else
{
vals[i] = 0;
}
}
right.build(vals);
for (int i = 1 ; i <= n ; ++i)
{
prefix[i] = prefix[i - 1];
if ((a[i] == 0 || b[i] >= D) && (c[i] == n + 1 || d[i] >= D))
{
prefix[i]++;
}
}
}
int ans = 0;
for (int i = L ; i <= R ; ++i)
{
if ((a[i] < L || b[i] >= D) && (c[i] > R || d[i] >= D))
{
ans++;
}
}
int add = 0;
int idx = sparse.findIDX(L, R);
if (a[idx] < L && c[idx] > R) add++;
if (a[idx] == 0 && c[idx] == n + 1) add++;
return prefix[R] - prefix[L - 1] + left.query(L, R, L) + (R - L + 1 - right.query(L, R, R + 1)) + add;
}
