#include<stdio.h>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
#include<vector>
#define lli long long int
using namespace std;
lli arr[1000008];
struct node
{
lli val;
lli index;
};
struct node tail[1000008];
int CeilIndex(lli l, lli r, lli key) {
int m;
while( r - l > 1 ) {
m = l + (r - l)/2;
(tail[m].val >= key ? r : l) = m; // ternary expression returns an l-value
}
return r;
}
lli condition(lli i,lli len)
{
/*printf("\n%lld - %lld<= %lld-%lld\n",
i,tail[len-1].index,arr[i],tail[len-1].val
);*/
if(i-tail[len-1].index<=arr[i]-tail[len-1].val)
return 1;
return 0;
}
lli fun(lli n)
{
/*printf("\n----------------------------\n");
for(lli i=0;i<n;i++)
{
printf("%lld ",tail[i].val);
}
printf("\n----------------------------\n");*/
}
lli lcs(lli n)
{
for(lli i=0;i<n;i++)
tail[i].val=-1;
// fun(n);
tail[0].val=arr[0];
tail[0].index=0;
lli len=1;
for(lli i=1;i<n;i++)
{
if(arr[i]<tail[0].val && condition(i,len))
{
//printf("Entering 1\n");
tail[0].val=arr[i];
tail[0].index=i;
}
else if(arr[i]>tail[len-1].val && condition(i,len))
{
// printf("Entering 2\n");
tail[len].val=arr[i];
tail[len].index=i;
len++;
}
else
{
// printf("Entering 3 && #%lld\n",condition(i,len));
lli z=CeilIndex(-1, len-1, arr[i]);
if(condition(i,z+1)==1)
{
tail[z].val=arr[i];
tail[z].index=i;
}
}
/* printf("\n----------------------------\n");
for(lli i=0;i<n;i++)
{
printf("%lld ",tail[i].val);
}
printf("\n----------------------------\n");*/
}
return n-len;
}
int main()
{
lli n;
scanf("%lld",&n);
for(lli i=0;i<n;i++)
{
scanf("%lld",&arr[i]);
}
lli ans=lcs(n);
/*printf("\nfinalfinal----------------------------\n");
for(lli i=0;i<n;i++)
{
printf("%lld ",tail[i].val);
}
printf("\n");
for(lli i=0;i<n;i++)
{
printf("%lld ",tail[i].index);
}
printf("\n----------------------------\n");*/
printf("%lld\n",ans);
}
I2luY2x1ZGU8c3RkaW8uaD4KI2luY2x1ZGU8c3RkbGliLmg+CiNpbmNsdWRlPGlvc3RyZWFtPgojaW5jbHVkZTxhbGdvcml0aG0+CiNpbmNsdWRlPHZlY3Rvcj4KI2RlZmluZSBsbGkgbG9uZyBsb25nIGludAp1c2luZyBuYW1lc3BhY2Ugc3RkOwpsbGkgYXJyWzEwMDAwMDhdOwpzdHJ1Y3Qgbm9kZQp7CiAgbGxpIHZhbDsKICBsbGkgaW5kZXg7Cn07CnN0cnVjdCBub2RlIHRhaWxbMTAwMDAwOF07CmludCBDZWlsSW5kZXgobGxpIGwsIGxsaSByLCBsbGkga2V5KSB7CiAgICBpbnQgbTsKCiAgICB3aGlsZSggciAtIGwgPiAxICkgewogICAgICAgIG0gPSBsICsgKHIgLSBsKS8yOwogICAgICAgICh0YWlsW21dLnZhbCA+PSBrZXkgPyByIDogbCkgPSBtOyAvLyB0ZXJuYXJ5IGV4cHJlc3Npb24gcmV0dXJucyBhbiBsLXZhbHVlCiAgICB9CgogICAgcmV0dXJuIHI7Cn0KbGxpIGNvbmRpdGlvbihsbGkgaSxsbGkgbGVuKQp7CiAgIC8qcHJpbnRmKCJcbiVsbGQgLSAlbGxkPD0gJWxsZC0lbGxkXG4iLAogICAgICAgICAgaSx0YWlsW2xlbi0xXS5pbmRleCxhcnJbaV0sdGFpbFtsZW4tMV0udmFsCiAgICAgICAgICApOyovCiAgIGlmKGktdGFpbFtsZW4tMV0uaW5kZXg8PWFycltpXS10YWlsW2xlbi0xXS52YWwpCiAgICByZXR1cm4gMTsKICAgcmV0dXJuIDA7Cn0KbGxpIGZ1bihsbGkgbikKewogIC8qcHJpbnRmKCJcbi0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS1cbiIpOwogICAgIGZvcihsbGkgaT0wO2k8bjtpKyspCiAgICAgewogICAgICAgcHJpbnRmKCIlbGxkICIsdGFpbFtpXS52YWwpOwogICAgIH0KICAgICBwcmludGYoIlxuLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLVxuIik7Ki8KfQpsbGkgbGNzKGxsaSBuKQp7CiAgZm9yKGxsaSBpPTA7aTxuO2krKykKICAgIHRhaWxbaV0udmFsPS0xOwogLy8gZnVuKG4pOwogIHRhaWxbMF0udmFsPWFyclswXTsKICB0YWlsWzBdLmluZGV4PTA7CiAgbGxpIGxlbj0xOwogIGZvcihsbGkgaT0xO2k8bjtpKyspCiAgewogICAgIGlmKGFycltpXTx0YWlsWzBdLnZhbCAmJiBjb25kaXRpb24oaSxsZW4pKQogICAgIHsKICAgICAgIC8vcHJpbnRmKCJFbnRlcmluZyAxXG4iKTsKICAgICAgIHRhaWxbMF0udmFsPWFycltpXTsKICAgICAgIHRhaWxbMF0uaW5kZXg9aTsKICAgICB9CiAgICAgZWxzZSBpZihhcnJbaV0+dGFpbFtsZW4tMV0udmFsICYmIGNvbmRpdGlvbihpLGxlbikpCiAgICAgewogICAgICAvLyAgIHByaW50ZigiRW50ZXJpbmcgMlxuIik7CiAgICAgICAgIHRhaWxbbGVuXS52YWw9YXJyW2ldOwogICAgICAgICB0YWlsW2xlbl0uaW5kZXg9aTsKICAgICAgICAgbGVuKys7CiAgICAgfQogICAgIGVsc2UKICAgICB7CgogICAgLy8gICAgcHJpbnRmKCJFbnRlcmluZyAzICYmICMlbGxkXG4iLGNvbmRpdGlvbihpLGxlbikpOwogICAgICAgIGxsaSB6PUNlaWxJbmRleCgtMSwgbGVuLTEsIGFycltpXSk7CiAgICAgICAgaWYoY29uZGl0aW9uKGkseisxKT09MSkKICAgICAgICB7CiAgICAgICAgICB0YWlsW3pdLnZhbD1hcnJbaV07CiAgICAgICAgICB0YWlsW3pdLmluZGV4PWk7CiAgICAgICAgfQogICAgIH0KICAgIC8qIHByaW50ZigiXG4tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tXG4iKTsKICAgICBmb3IobGxpIGk9MDtpPG47aSsrKQogICAgIHsKICAgICAgIHByaW50ZigiJWxsZCAiLHRhaWxbaV0udmFsKTsKICAgICB9CiAgICAgcHJpbnRmKCJcbi0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS1cbiIpOyovCiAgfQogIHJldHVybiBuLWxlbjsKfQppbnQgbWFpbigpCnsKICBsbGkgbjsKICBzY2FuZigiJWxsZCIsJm4pOwogIGZvcihsbGkgaT0wO2k8bjtpKyspCiAgewogICAgc2NhbmYoIiVsbGQiLCZhcnJbaV0pOwogIH0KICBsbGkgYW5zPWxjcyhuKTsKICAgLypwcmludGYoIlxuZmluYWxmaW5hbC0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS1cbiIpOwogICAgIGZvcihsbGkgaT0wO2k8bjtpKyspCiAgICAgewogICAgICAgcHJpbnRmKCIlbGxkICIsdGFpbFtpXS52YWwpOwogICAgIH0KICAgICBwcmludGYoIlxuIik7CiAgICAgZm9yKGxsaSBpPTA7aTxuO2krKykKICAgICB7CiAgICAgICBwcmludGYoIiVsbGQgIix0YWlsW2ldLmluZGV4KTsKICAgICB9CiAgICAgcHJpbnRmKCJcbi0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS1cbiIpOyovCgogIHByaW50ZigiJWxsZFxuIixhbnMpOwp9Cg==