Almost Increasing Array

배열에서 하나 이하의 원소를 지워 배열을 엄격히 증가하게 만들 수 있다면(즉, 모든 원소가 그 앞의 모든 원소보다 엄격히 크다면), 이 배열을 거의 증가하는 배열이라고 한다.

n개의 원소로 이루어진 배열 a가 주어진다. 어떤 원소든 임의의 정수로 바꿀 수 있으며, 필요한 만큼 여러 번 바꿀 수 있다. 배열을 거의 증가하게 만들기 위해 수행해야 하는 교체의 최소 횟수는 얼마인가?

첫째 줄에 a의 원소 개수를 나타내는 하나의 정수 n (2 ≤ n ≤ 200000)이 주어진다.

둘째 줄에 배열 a를 나타내는 n개의 정수 a1, a2, ..., an (1 ≤ ai ≤ 109)이 주어진다.

a를 거의 증가하게 만들기 위해 수행해야 하는 교체의 최소 횟수를 출력한다.