#include <bits/stdc++.h>
#include "towers.h"
using namespace std;
#define fi first
#define se second
typedef long long ll;
typedef long double ld;
mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
int inf = 1e9;
int n;
vector<int> h;
vector<int> prefdpsm, prefdpbi;
void init(int N, vector<int> H) {
n = N;
h = H;
prefdpsm.assign(n + 1, 0);
prefdpbi.assign(n + 1, 0);
vector<int> smaller(n, -1), bigger(n, -1);
vector<int> s;
for (int i = 0; i < n; i++) {
while (!s.empty() && h[s.back()] >= h[i]) {
s.pop_back();
}
if (!s.empty()) {
smaller[i] = s.back();
}
s.push_back(i);
}
s.clear();
for (int i = 0; i < n; i++) {
while (!s.empty() && h[s.back()] <= h[i]) {
s.pop_back();
}
if (!s.empty()) {
bigger[i] = s.back();
}
s.push_back(i);
}
vector<pair<int, int>> dp(n, {1, 0});
for (int i = 0; i < n; i++) {
if (smaller[i] != -1) {
dp[i].se = max(dp[i].se, dp[smaller[i]].fi);
}
if (bigger[i] != -1) {
dp[i].fi = max(dp[i].fi, dp[bigger[i]].se + 1);
}
}
for (int i = 0; i < n; i++) {
prefdpsm[i + 1] = max(prefdpsm[i], dp[i].fi);
prefdpbi[i + 1] = max(prefdpbi[i], dp[i].se);
}
}
int max_towers(int l, int r, int d) {
int res = prefdpsm[r + 1] - prefdpbi[l + 1];
return res;
}
