Min Deletions to Almost Sorted

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. In the original example explanation, "delete 7" should be "delete 1".

输入格式

The input gives n and n distinct integers. Full original bounds: 1≤n≤100000, 1≤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.