Almost Increasing Array

题意翻译

### 题目描述 定义一个序列$A$是$Almost\;Increasing$的,当$A$满足从$A$中去掉一个位置之后剩下的序列形成了一个严格递增序列。 给出一个长度为$n$的序列,问最小需要改动多少个位置的值,使得这个序列变成$Almost\;Increasing$的。 ### 数据范围 $2\le n\le 200000,\quad 1\le a_i \le 10^9$

题目描述

We call an array almost increasing if we can erase not more than one element from it so that the array becomes strictly increasing (that is, every element is striclty greater than every element before it). You are given an array $ a $ consisting of $ n $ elements. You are allowed to replace any element with any integer number (and you may do so any number of times you need). What is the minimum number of replacements you have to perform in order to make the array almost increasing?

输入输出格式

输入格式


The first line contains one integer $ n $ ( $ 2<=n<=200000 $ ) — the number of elements in $ a $ . The second line contains $ n $ integers $ a_{1} $ , $ a_{2} $ , ..., $ a_{n} $ ( $ 1<=a_{i}<=10^{9} $ ) — the array $ a $ .

输出格式


Print the minimum number of replaces you have to perform so that $ a $ is almost increasing.

输入输出样例

输入样例 #1

5
5 4 3 2 1

输出样例 #1

3

输入样例 #2

5
1 2 8 9 5

输出样例 #2

0