#include <cstdio>
#ifdef DEBUG
#define D(X) X
#else
#define D(X)
#endif
#include <bits/stdc++.h>
#define fr first
#define sc second
#define ll long long
#define pi 3.14159265359
#define pub push_back
#define pob pop_back
#define pari pair<int,int>
#define parli pair<long, long>
using namespace std;
const int INF = 1000 * 1000 * 1000;
const ll INF2 = 1LL * 1000 * 1000 * 1000 * 1000 * 1000 * 1000;
const int mod = 1000 * 1000 * 1000 + 7;
bool comp(pari& v1, pari& v2)
{
return v1.fr < v2.fr;
}
struct seg {
vector<int> tree;
int sz;
void build(int n) {
sz = 1;
while(sz<n) {
sz *= 2;
}
tree.resize(2*sz + 1, 0);
}
void clean()
{
for(int i=0; i<tree.size(); i++) {
tree[i] = 0;
}
}
void recSet(int idx, int lx, int rx, int i, int val) {
if(rx-lx==1) {
tree[idx] = val;
return;
}
int mid = (lx+rx)/2;
if(i<mid) {
recSet(2*idx+1, lx, mid, i, val);
} else
{
recSet(2*idx+2, mid, rx, i, val);
}
tree[idx] = max(tree[2*idx+1], tree[2*idx+2]);
}
void setX(int i, int val) {
recSet(0, 0, sz, i, val);
}
int rec_range(int idx, int lx, int rx, int l, int r) {
if(lx>=l&&rx<=r) {
return tree[idx];
}
if(rx<=l||lx>=r) return 0;
int mid = (lx+rx)/2;
int left = rec_range(2*idx+1, lx, mid, l, r);
int right = rec_range(2*idx+2, mid, rx, l, r);
return max(left, right);
}
int range(int l, int r) {
if(l>=r) {
return 0;
}
return rec_range(0, 0, sz, l, r);
}
};
struct seg2 {
vector<int> tree;
int sz;
void build(int n) {
sz = 1;
while(sz<n) {
sz *= 2;
}
tree.resize(2*sz + 1, INF);
}
void clean()
{
for(int i=0; i<tree.size(); i++) {
tree[i] = INF;
}
}
void recSet(int idx, int lx, int rx, int i, int val) {
if(rx-lx==1) {
tree[idx] = val;
return;
}
int mid = (lx+rx)/2;
if(i<mid) {
recSet(2*idx+1, lx, mid, i, val);
} else
{
recSet(2*idx+2, mid, rx, i, val);
}
tree[idx] = min(tree[2*idx+1], tree[2*idx+2]);
}
void setX(int i, int val) {
recSet(0, 0, sz, i, val);
}
int rec_range(int idx, int lx, int rx, int l, int r) {
if(lx>=l&&rx<=r) {
return tree[idx];
}
if(rx<=l||lx>=r) return INF;
int mid = (lx+rx)/2;
int left = rec_range(2*idx+1, lx, mid, l, r);
int right = rec_range(2*idx+2, mid, rx, l, r);
return min(left, right);
}
int range(int l, int r) {
return rec_range(0, 0, sz, l, r);
}
int low1(int idx, int lx, int rx, int l, int r, int val, int dir)
{
if(tree[idx]>=val||l>=rx||lx>=r) {
if(dir==0)
return -1;
return INF;
}
if(rx-lx==1) {
return lx;
}
int mid = (lx+rx)/2;
int id1, id2;
if(dir==1) {
id1 = low1(2*idx+1, lx, mid, l, r, val, dir);
if(id1>=l&&id1<r) {
return id1;
}
id2 = low1(2*idx+2, mid, rx, l, r, val, dir);
return min(id1, id2);
}
id2 = low1(2*idx+2, mid, rx, l, r, val, dir);
if(id2>=l&&id2<r) {
return id2;
}
id1 = low1(2*idx+1, lx, mid, l, r, val, dir);
return max(id1, id2);
}
int low1(int l, int r, int val, int dir)
{
return low1(0, 0, sz, l, r, val, dir);
}
};
vector<int> dp;
seg mint, maxt, st2;
map<int, int> ord;
vector<int> h;
int res = 0;
int center = -1;
vector<int> pref, left1, right1, difh;
int qcnt = 0;
seg2 st1;
void init2(int l, int r, int d)
{
int n = h.size();
res = 0;
for(int i=0; i<=n; i++) {
dp[i] = 0;
}
vector<int> used(n+1, 0);
vector<int> nums;
for(int i=l; i<=r; i++) {
int f1 = 0, f2 = 0;
nums.pub(h[i]);
nums.pub(h[i]-d);
nums.pub(h[i]+d);
if(i>l) {
if(h[i]>=h[i-1]) {
f1 = 1;
} else
{
f1 = 2;
}
}
if(i<r) {
if(h[i]>=h[i+1]) {
f2 = 1;
} else
{
f2 = 2;
}
}
if(f1==0) {
f1 = f2;
}
if(f2==0) {
f2 = f1;
}
if(f1==f2) {
used[i] = f1;
}
}
sort(nums.begin(), nums.end());
ord.clear();
ord[nums[0]] = 0;
int sz = nums.size();
for(int i=1; i<sz; i++) {
if(nums[i]>nums[i-1]) {
ord[nums[i]] = ord[nums[i-1]] + 1;
} else
{
ord[nums[i]] = ord[nums[i-1]];
}
}
mint.clean();
maxt.clean();
mint.build(sz);
maxt.build(sz);
for(int i=r; i>=l; i--) {
if(used[i]==0) {
continue;
}
if(used[i]==1&&h[i]-d>0) {
dp[i] = mint.range(0, ord[h[i]-d] + 1);
maxt.setX(ord[h[i]], dp[i]);
}
if(used[i]==2) {
dp[i] = 1 + maxt.range(ord[h[i]+d], sz);
mint.setX(ord[h[i]], dp[i]);
}
res = max(res, dp[i]);
}
}
void calc_pref()
{
int n = h.size();
pref.resize(n+1);
pref[0] = 0;
for(int i=1; i<=n; i++) {
pref[i] = pref[i-1];
if(i>1&&i<n) {
if(h[i-1]<h[i-2]&&h[i-1]<h[i]) {
pref[i]++;
}
} else if(i>1)
{
if(h[i-1]<h[i-2]) {
pref[i]++;
}
} else
{
if(h[i-1]<h[i]) {
pref[i]++;
}
}
}
}
void all_arr()
{
int n = h.size();
left1.resize(n, INF);
right1.resize(n, -1);
st1.build(n);
st2.build(n);
for(int i=0; i<n; i++) {
st1.setX(i, h[i]);
st2.setX(i, h[i]);
}
difh.resize(n);
for(int i=0; i<n; i++) {
pari p = {h[i], i};
left1[p.sc] = st1.low1(0, p.sc, p.fr, 0);
right1[p.sc] = st1.low1(p.sc + 1, n, p.fr, 1);
int h1 = 2*INF+10, h2 = h1;
if(left1[p.sc]!=-1) {
h1 = st2.range(left1[p.sc]+1, p.sc);
}
if(right1[p.sc]!=INF) {
h2 = st2.range(p.sc+1, right1[p.sc]);
} //cout<<h1<<endl;
difh[p.sc] = min(h1, h2) - p.fr;
}
sort(difh.begin(), difh.end());
}
void init(int n, vector<int> h2)
{
h.resize(n);
for(int i=0; i<n; i++) {
h[i] = h2[i];
}
dp.resize(n+1);
int idx = 1;
while(idx<n&&h[idx]>=h[idx-1]) {
idx++;
}
center = idx - 1;
while(idx<n&&h[idx]<=h[idx-1]) {
idx++;
}
calc_pref();
if(idx==n) {
return;
}
center = -1;
}
int max_towers(int l, int r, int d)
{
qcnt++;
int n = h.size();
if(n==1) {
return 1;
}
if(l==r) {
return 1;
}
if(center!=-1) {
if(r<=center||l>=center) {
return 1;
}
if(h[center]-h[l]>=d&&h[center]-h[r]>=d) {
return 2;
}
return 1;
}
if(d==1) {
if(pref.size()==0) {
calc_pref();
}
int ans = pref[r] - pref[l+1];
if(h[l]<h[l+1]) {
ans++;
}
if(h[r]<h[r-1]) {
ans++;
}
return ans;
}
/*
for(int i=0; i<n; i++) {
//cout<<left1[i]<<" ";
//cout<<right1[i]<<" ";
//cout<<difh[i]<<" ";
}
//cout<<endl;
*/
if(l==0&&r==h.size()-1) {
if(qcnt==1) {
all_arr();
}
int lo = 0, hi = n - 1;
while(lo<=hi) {
int mid = (lo+hi)/2;
if(difh[mid]>=d) {
hi = mid - 1;
} else
{
lo = mid + 1;
}
}
return n - lo;
}
if(qcnt==1) {
qcnt = 7;
init2(l, r, d);
return res;
}
return res;
}
/*
7
10 20 60 40 50 30 70
*/
/*
int main()
{
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
//D(freopen("input.txt","r",stdin);)
//D(freopen("ouput.txt","w",stdout);)
int t = 1;
//cin >> t;
loop:
while(t--)
{
int n;
cin >> n;
vector<int> a(n);
for(int i=0; i<n; i++) {
cin >> a[i];
}
init(n, a);
int res = max_towers(0, 6, 10);
if(res==0) {
res = 1;
}
cout << res;
}
return 0;
}
*/
