#include "towers.h"
#include <vector>
using namespace std;
const int N = 100000;
int abs_(int a) { return a > 0 ? a : -a; }
int max(int a, int b) { return a > b ? a : b; }
typedef vector<int> vi;
int dd[N], iq[N + 1], pq[N], cnt;
int lt(int i, int j) { return dd[i] < dd[j]; }
int p2(int p) {
return (p *= 2) > cnt ? 0 : (p < cnt && lt(iq[p + 1], iq[p]) ? p + 1 : p);
}
void pq_up(int i) {
int p, q, j;
for (p = pq[i]; (q = p / 2) && lt(i, j = iq[q]); p = q)
iq[pq[j] = p] = j;
iq[pq[i] = p] = i;
}
void pq_dn(int i) {
int p, q, j;
for (p = pq[i]; (q = p2(p)) && lt(j = iq[q], i); p = q)
iq[pq[j] = p] = j;
iq[pq[i] = p] = i;
}
void pq_add(int i) {
pq[i] = ++cnt, pq_up(i);
}
int pq_remove_first() {
int i = iq[1], j = iq[cnt--];
if (j != i)
pq[j] = 1, pq_dn(j);
pq[i] = 0;
return i;
}
void pq_remove(int i) {
int j = iq[cnt--];
if (j != i)
pq[j] = pq[i], pq_up(j), pq_dn(j);
pq[i] = 0;
}
int aa[N], ii[N], ii_[N], ll[N], rr[N], pp[N], qq[N], n, p, k, k_, 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;
k = 0;
ii[k++] = 0;
for (int i = 1; i < n; i++)
if (k % 2 != 0) {
if (aa[ii[k - 1]] > aa[i])
ii[k - 1] = i;
else
ii[k++] = i;
} else {
if (aa[ii[k - 1]] < aa[i])
ii[k - 1] = i;
else
ii[k++] = i;
}
if (k % 2 == 0)
k--;
for (int h = 0; h < k; h++)
pp[ii[h]] = h == 0 ? -1 : ii[h - 1], qq[ii[h]] = h + 1 == k ? n : ii[h + 1];
for (int h = 0; h + 1 < k; h++)
dd[ii[h]] = abs_(aa[ii[h + 1]] - aa[ii[h]]), pq_add(ii[h]);
k = 0;
while (cnt) {
int i = pq_remove_first(), j = qq[i];
if (pp[i] == -1) {
pq_remove(j);
pp[qq[j]] = -1;
} else if (qq[j] == n) {
pq_remove(pp[i]);
qq[pp[i]] = n;
} else {
pq_remove(pp[i]), pq_remove(j);
qq[pp[i]] = qq[j], pp[qq[j]] = pp[i];
dd[pp[i]] = abs_(aa[qq[j]] - aa[pp[i]]), pq_add(pp[i]);
}
if (aa[i] > aa[j])
ii[k++] = i;
else
dd[j] = dd[i], ii[k++] = j;
}
}
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 (l == 0 && r == n - 1) {
int lower = -1, upper = k;
while (upper - lower > 1) {
int h = (lower + upper) / 2;
if (dd[ii[h]] < d)
lower = h;
else
upper = h;
}
return k - upper + 1;
} else {
if (first) {
k_ = 0;
ii_[k_++] = 0;
for (int i = 1; i < n; i++)
if (k_ % 2 != 0) {
if (aa[ii_[k_ - 1]] > aa[i])
ii_[k_ - 1] = i;
else if (aa[i] - aa[ii_[k_ - 1]] >= d)
ii_[k_++] = i;
} else {
if (aa[ii_[k_ - 1]] < aa[i])
ii_[k_ - 1] = i;
else if (aa[ii_[k_ - 1]] - aa[i] >= d)
ii_[k_++] = i;
}
for (int h = 1; h < k_ - 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;
}
}
k_ = (k_ - 1) / 2;
first = 0;
}
int lower, upper;
lower = -1, upper = k_;
while (upper - lower > 1) {
int h = (lower + upper) / 2;
if (l <= ll[h])
upper = h;
else
lower = h;
}
l = upper;
lower = -1, upper = k_;
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;
}
}
