#include "towers.h"
#include <vector>
using namespace std;
const int N = 100000;
int max(int a, int b) { return a > b ? a : b; }
typedef vector<int> vi;
int aa[N], ii[N], ll[N], rr[N], n, p, cnt;
int first;
void init(int n_, vi aa_) {
n = n_;
for (int i = 0; i < n; i++)
aa[i] = aa_[i];
p = 0;
while (p < n - 1 && aa[p] < aa[p + 1])
p++;
for (int i = p + 1; i < n; i++)
if (aa[i - 1] < aa[i]) {
p = -1;
break;
}
first = 1;
}
int max_towers(int l, int r, int d) {
if (p != -1)
return l < p && p < r && aa[p] - aa[l] >= d && aa[p] - aa[r] >= d ? 2 : 1;
else {
if (first) {
cnt = 0;
ii[cnt++] = 0;
for (int i = 1; i < n; i++)
if (cnt % 2 != 0) {
if (aa[ii[cnt - 1]] > aa[i])
ii[cnt - 1] = i;
else if (aa[i] - aa[ii[cnt - 1]] >= d)
ii[cnt++] = i;
} else {
if (aa[ii[cnt - 1]] < aa[i])
ii[cnt - 1] = i;
else if (aa[ii[cnt - 1]] - aa[i] >= d)
ii[cnt++] = i;
}
for (int h = 1; h < cnt - 1; h += 2) {
for (int i = ii[h] - 1; i >= 0; i--)
if (aa[ii[h]] - aa[i] >= d) {
ll[h / 2] = i;
break;
}
for (int i = ii[h] + 1; i < n; i++)
if (aa[ii[h]] - aa[i] >= d) {
rr[h / 2] = i;
break;
}
}
cnt = (cnt - 1) / 2;
first = 0;
}
int lower, upper;
lower = -1, upper = cnt;
while (upper - lower > 1) {
int h = (lower + upper) / 2;
if (l <= ll[h])
upper = h;
else
lower = h;
}
l = upper;
lower = -1, upper = cnt;
while (upper - lower > 1) {
int h = (lower + upper) / 2;
if (rr[h] <= r)
lower = h;
else
upper = h;
}
r = lower;
return max(r - l + 1, 0) + 1;
}
}
