Min Elements to Remove to Make Almost Sorted Array

The array elements are distinct. An array is called almost increasing if and only if deleting at most one more element makes it strictly increasing. Find the minimum number of elements to delete from the given array so that the remaining array is almost increasing. The original text mistakenly joined [13] and [9,2] into [13,9,2] and called it valid; this is corrected according to the full definition and the identical problem 29: three decreasing items are not almost increasing.

输入格式

The input gives n and n distinct integers. The original gives no numeric bounds; this site adds 1≤n≤100000, −10^9≤a[i]≤10^9.

输出格式

Output one integer answer.

样例 1

输入：

5
3 4 2 5 1

输出：

1

样例 2

输入：

3
4 2 1

输出：

1

样例 3

输入：

1
13

输出：

0

样例说明

The outputs of the three public examples are, in order: 1; 1; 0. They have been checked by independent enumeration or direct simulation.