#include "towers.h"
#include <vector>
#include <algorithm>
#include <iostream>
#include <cmath>
#include <queue>
using namespace std;
namespace {
int N, K;
int H[100005];
}
void init(int N, std::vector<int> H) {
::N = N;
::K = -1;
for (int i = 0; i < N; i++) {
::H[i] = H[i];
}
}
int dp[100005];
struct maxseg
{
vector<int> tree;
maxseg(int n)
{
int sz = 1 << ((int)ceil(log2(n))+1);
tree.resize(sz);
}
int init(int s, int e, int node, vector<int> &vc)
{
if (s == e) return tree[node] = vc[s];
else return tree[node] = max(init(s, (s+e)/2, 2*node, vc), init((s+e)/2+1, e, 2*node+1, vc));
}
void upd(int s, int e, int node, int id, int val)
{
if (e < id || id < s) return;
if (s == e) {
tree[node] = val;
return;
}
upd(s, (s+e)/2, 2*node, id, val);
upd((s+e)/2+1, e, 2*node+1, id, val);
tree[node] = max(tree[2*node], tree[2*node+1]);
}
int query(int s, int e, int node, int l, int r)
{
if (e < l || r < s) return 0;
if (l <= s && e <= r) return tree[node];
return max(query(s, (s+e)/2, 2*node, l, r), query((s+e)/2+1, e, 2*node+1, l, r));
}
};
int max_towers(int L, int R, int D) {
int M = R - L + 1;
vector<int> A(M);
for (int i = L; i <= R; i++) A[i - L] = H[i];
maxseg seg(M), seg2(M);
seg.init(0, M-1, 1, A);
dp[0] = 1;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
pq.push(make_pair(A[0], 0));
for (int i = 1; i < M; i++) {
//키가 A[i] - D 이하인 애들을 모두 해방시키자
while (!pq.empty() && pq.top().first <= A[i] - D) {
seg2.upd(0, M-1, 1, pq.top().second, dp[pq.top().second]);
pq.pop();
}
int l = 0, r = i - 1; //max(k ... i) >= A[i] + D인 최대 k 찾기
while (l < r) {
int m = l + r + 1 >> 1;
if (seg.query(0, M-1, 1, m, i) >= A[i] + D) {
l = m;
}
else r = m - 1;
}
if (seg.query(0, M-1, 1, l, i) < A[i] + D) l = -1;
dp[i] = seg2.query(0, M-1, 1, 0, l) + 1;
pq.push(make_pair(A[i], i));
}
int ans = 0;
for (int i = 0; i < M; i++) ans = max(ans, dp[i]);
return ans;
//0부터 M-1까지 A에서 문제 풀기
}
