#include #define rep(i,a,b) for(int i=a;i=b;i--) #define fore(i,a) for(auto &i:a) #define all(x) (x).begin(),(x).end() #pragma GCC optimize ("-O3") using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); } typedef long long ll; const int inf = INT_MAX / 2; const ll infl = 1LL << 60; templatebool chmax(T &a, const T &b) { if (abool chmin(T &a, const T &b) { if (b=b;i--) struct LIS { vector& v; vector dp, id, ret, info; // info 1:unused 2:使っても良い 3:必ず使う int n; int lis; LIS(vector& _v) : v(_v) { n = v.size(); dp.resize(n, INT_MAX / 2); id.resize(n, 0); rep(i, 0, n-1) { // 狭義単調増加列 //id[i] = lower_bound(dp.begin(), dp.end(), v[i]) - dp.begin(); // 広義単調増加列 id[i] = upper_bound(dp.begin(), dp.end(), v[i]) - dp.begin(); dp[id[i]] = v[i]; } int nl = *max_element(id.begin(), id.end()); lis = nl; ret.resize(nl + 1, 0); rrep(i, n - 1, 0) if (id[i] == nl) ret[nl] = v[i], nl--; info.resize(n); vector ma(n + 1), cnt(n); ma[lis] = INT_MAX / 2; rrep(i, n - 1, 0) { // 狭義単調増加列 //if (ma[id[i] + 1] <= v[i]) info[i] = 1; // 広義単調増加列 if (ma[id[i] + 1] < v[i]) info[i] = 1; else cnt[id[i]]++, ma[id[i]] = max(ma[id[i]], v[i]); } rrep(i, n - 1, 0) if (info[i] == 0 && cnt[id[i]] == 1) info[i] = 3; rep(i, 0, n) if (info[i] == 0) info[i] = 2; } }; /*---------------------------------------------------------------------------------------------------             ∧_∧       ∧_∧  (´<_` )  Welcome to My Coding Space!      ( ´_ゝ`) /  ⌒i     /   \    | |     /   / ̄ ̄ ̄ ̄/  |   __(__ニつ/  _/ .| .|____      \/____/ (u ⊃ ---------------------------------------------------------------------------------------------------*/ int N, A[201010]; //--------------------------------------------------------------------------------------------------- void _main() { cin >> N; rep(i, 0, N) cin >> A[i]; vector v; v.push_back(-inf); rep(i, 0, N) v.push_back(A[i] - i); v.push_back(inf); //fore(i, v) printf("%d ", i); //printf("\n"); LIS lis(v); int ans = N - lis.lis; //cout << lis.lis << endl; cout << ans << endl; }