Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official.
×

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ACM-ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

G. Almost Increasing Array

time limit per test

3 secondsmemory limit per test

512 megabytesinput

standard inputoutput

standard outputWe 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?

Input

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*.

Output

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

Examples

Input

5

5 4 3 2 1

Output

3

Input

5

1 2 8 9 5

Output

0

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/18/2018 17:22:43 (d1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|