#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define ld long double
#define ull unsigned long long
#define ff first
#define ss second
#define pii pair<int,int>
#define pll pair<long long, long long>
#define vi vector<int>
#define vl vector<long long>
#define pb push_back
#define rep(i, b) for(int i = 0; i < (b); ++i)
#define rep2(i,a,b) for(int i = a; i <= (b); ++i)
#define rep3(i,a,b,c) for(int i = a; i <= (b); i+=c)
#define count_bits(x) __builtin_popcountll((x))
#define all(x) (x).begin(),(x).end()
#define siz(x) (int)(x).size()
#define forall(it,x) for(auto& it:(x))
using namespace __gnu_pbds;
using namespace std;
typedef tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update> ordered_set;
//mt19937 mt;void random_start(){mt.seed(chrono::time_point_cast<chrono::milliseconds>(chrono::high_resolution_clock::now()).time_since_epoch().count());}
//ll rand(ll a, ll b) {return a + (mt() % (b-a+1));}
const int INF = 1e9+50;
const ll INF_L = 1e18+40;
const ll MOD = 1e9+7;
const int tree_siz = (1 << 15)-1;
int drzewo[tree_siz];
int get_max(int akt, int p1, int p2, int s1, int s2)
{
if(p2 < s1 || p1 > s2) return -1e5;
if(p1 >= s1 && p2 <= s2) return drzewo[akt-1];
return max(get_max(akt*2,p1,(p1+p2)/2,s1,s2),get_max(akt*2+1,(p1+p2)/2+1,p2,s1,s2));
}
void upd(int v)
{
drzewo[v-1]= max(drzewo[v*2-1],drzewo[v*2]);
if(v != 1) upd(v/2);
}
void change(int ind, int x, bool is_set = false)
{
drzewo[tree_siz/2+ind] = max(drzewo[tree_siz/2+ind],x);
if(is_set) drzewo[tree_siz/2+ind] = x;
upd((tree_siz/2+ind+1)/2);
}
struct event
{
int sort_poz, poz, val, ind, type;
bool operator<(const event& e)
{
if(sort_poz != e.sort_poz) return sort_poz < e.sort_poz;
if(poz != e.poz) return poz < e.poz;
return type < e.type;
}
};
pii rotateP(pii point)
{
return {-point.ss,point.ff};
}
struct square
{
vector<pii> points;
square(pii corner, int len)
{
points.pb(corner);
points.pb({corner.ff,corner.ss-len});
points.pb({corner.ff-len,corner.ss-len});
points.pb({corner.ff-len,corner.ss});
}
void rotate()
{
rep(i,4) points[i] = rotateP(points[i]);
swap(points[0],points[1]);
swap(points[1],points[2]);
swap(points[2],points[3]);
}
};
vector<square> squ;
vector<square> new_squ;
vector<pii> vp;
int min_side[100000];
int main()
{
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
//random_start();
rep(i,tree_siz) drzewo[i] = -1e5;
int n;
cin >> n;
rep2(i,1,n)
{
int x;
cin >> x;
square new_s({i,x},0);
new_squ.pb(new_s);
vp.pb({i,x});
}
int ans = n;
vector<event> events;
while(!new_squ.empty())
{
ans--;
swap(new_squ,squ);
new_squ = {};
// cout << ans << " iter:\n\nsqu:\n";
// forall(it,squ)
// {
// cout << it.points[0].ff << " " << it.points[0].ss << " " << it.points[0].ss - it.points[1].ss << " squ\n";
// }
rep(ang,4)
{
events = {};
rep(i,siz(squ))
{
events.pb({squ[i].points[0].ss - squ[i].points[0].ff,squ[i].points[0].ff+n,squ[i].points[1].ss,i,1});
}
rep(i,n)
{
min_side[i] = 1e9;
events.pb({vp[i].ss-vp[i].ff,vp[i].ff+n,-1,i,0});
}
sort(all(events));
forall(it,events)
{
if(it.type == 1)
{
// if(ang == 1) cout << it.poz << " " << it.val << " " << it.ind << " val\n";
change(it.poz,it.val);
}
else
{
int m = get_max(1,0,tree_siz/2,0,it.poz-1);
// if(ang == 1) cout << it.ind << " " << it.poz << " " << vp[it.ind].ff << " " << vp[it.ind].ss << " " << m << " ans2\n";
min_side[it.ind] = min(min_side[it.ind],vp[it.ind].ss - m);
}
// cout << it.ind << " first\n";
}
forall(it,events)
{
if(it.type == 1)
change(it.poz,-1e5,1);
}
events = {};
rep(i,siz(squ))
{
events.pb({-(squ[i].points[0].ss - squ[i].points[0].ff),squ[i].points[0].ss+n,squ[i].points[2].ff,i,1});
}
rep(i,n)
{
events.pb({-(vp[i].ss-vp[i].ff),vp[i].ss+n,-1,i,0});
}
sort(all(events));
forall(it,events)
{
if(it.type == 1)
{
change(it.poz,it.val);
}
else
{
int m = get_max(1,0,tree_siz/2,0,it.poz-1);
// cout << it.ind << " " << m << " ans2\n";
min_side[it.ind] = min(min_side[it.ind],vp[it.ind].ff - m);
}
// cout << it.ind << " second\n";
}
forall(it,events)
{
if(it.type == 1)
change(it.poz,-1e5,1);
}
rep(i,n)
{
// if(ang == 1) cout << min_side[i] << " " << ang << " " << i << " " << vp[i].ff << " " << vp[i].ss << " min_side\n";
if(min_side[i] <= 10000)
{
square new_s(vp[i],min_side[i]);
new_squ.pb(new_s);
}
}
rep(i,n)
{
vp[i] = rotateP(vp[i]);
}
rep(i,siz(new_squ))
{
new_squ[i].rotate();
}
rep(i,siz(squ))
{
squ[i].rotate();
}
// cout << "\nnew angle\n";
}
// cout << " new_squ:\n";
squ = {};
forall(it,new_squ)
{
bool is_ok = true;
forall(it2,it.points)
{
if(it2.ff < 1 || it2.ff > n) is_ok = false;
if(it2.ss < 1 || it2.ss > n) is_ok = false;
}
if(is_ok)
{
squ.pb(it);
// cout << it.points[0].ff << " " << it.points[0].ss << " " << it.points[0].ss - it.points[1].ss << " new_squ\n";
}
}
new_squ = squ;
// if(ans == 7) break;
}
cout << ans << "\n";
}
