There are $N$ cards laid out. For convenience, let the leftmost card be card 1, the next card be card 2, $\dots$, and the rightmost card be card $N$.

Each of the $N$ cards has an integer written on it. Let $x_i$ be the number written on card $i$.

We want to properly change the numbers written on some of the $N$ cards so that, from left to right, the numbers written on the cards increase by a constant amount, decrease by a constant amount, or are all equal.

When changing the numbers written on the cards, they can only be changed to integer values, and the number of changes must be minimized.

For example, suppose the cards are given as shown in the figure below.

In this case, changing the number written on card 3 to 3 allows them to increase by 1 as shown below, and the number of cards whose written numbers were changed is 1.

It is also possible to make the numbers written on all cards equal to 2, as shown below. In this case, the number of cards whose written numbers were changed is 2.

Given the numbers written on each card in order from the leftmost card to the rightmost card, find the minimum number of cards that must be changed to satisfy the condition.

Constraints

• $2 \le N \le 500$
• For all $1 \le i \le N$, $-1\ 000\ 000 \le x_i \le 1\ 000\ 000$

Subtasks

1. (3 points) $N \le 3$.
2. (10 points) The answer is at most 2.
3. (20 points) It is guaranteed that there exists a case where the difference between the numbers written on adjacent cards is at most 100 when the condition is satisfied by changing the minimum number of cards.
4. (67 points) No additional constraints.

Input

The first line contains the number of cards $N$.

The second line contains the numbers $x_i$ written on each card in order, separated by spaces.

Output

Print the answer on the first line.

Examples

Examples

Input 1

4
1 2 2 4

Output 1

1

Examples

Input 2

5
6 3 3 1 -1

Output 2

2