#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
int k = 0;
vector<int> h;
vector<pair<int, int>> dp;
int n;
void init (int n1, vector<int> h1){
n = n1;
h = h1;
}
void update(int st, int l, int r, int indx, pair<int, int> c){
if(l == r && l == indx){
dp[st] = c;
return;
}
int mid = (l+r)/2;
if(indx <= mid) update(st*2+1, l, mid, indx, c);
if(indx > mid) update(st*2+2, mid+1, r, indx, c);
dp[st].first = max(dp[st*2+1].first, dp[st*2+2].first);
dp[st].second = max(dp[st*2+1].second, dp[st*2+2].second);
}
int query(int st, int l, int r, int a, int b, int md){
if(a>b) return 0;
if(l>r) return 0;
if(a == l && b == r){
if(md == 0) return dp[st].first;
else return dp[st].second;
}
int mid = (l+r)/2;
int ret = 0;
if(a <= mid) ret = max(ret, query(st*2+1, l, mid, a, min(b, mid), md));
if(b>mid) ret = max(ret, query(st*2+2, mid+1, r, max(mid+1, a), b, md));
return ret;
}
int max_towers(int l, int r, int d){
dp.assign(3*n, {0, 0});
vector<int> sortedH;
for(int i = l; i<=r; i++) sortedH.push_back(h[i]);
sort(sortedH.begin(), sortedH.end());
int ans = 1;
for(int i = l; i<=r; i++){
int indx = lower_bound(sortedH.begin(), sortedH.end(), h[i]) - sortedH.begin();
int maxR = query(0, 0, r-l, indx+1, r - l, 1);
int maxL = query(0, 0, r-l, 0, indx-1, 0);
update(0, 0, r-l, indx, {maxR+1, maxL});
ans = max(ans, maxR+1);
}
return ans;
}
