Page not loading? Try clicking here.
Placeholder

#5196
Subtask

Change card 1s 32MB

Problems

There are N cards.

For convenience, let the leftmost card be card 1, the next card be card 2, ..., and the rightmost card be card N.

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

By appropriately changing the numbers written on some of the N cards, 

we want the numbers written on the cards to increase at a constant rate, decrease at a constant rate, or all be the same from left to right.

When changing the numbers 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, if the number on card 3 is changed to 3, they can be made to increase by 1 as shown below, and the number of cards with changed values is 1.

It is also possible to make the numbers on all cards 2 as follows. In this case, the number of cards with changed values 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.​


Input

In the first line, the number of cards N is given.

In the second line, the numbers x_i written on each card are given in order, separated by spaces.

[Constraints]

2 \le N \le 500

For all 1 \le i \le N, -1,000,000 \le x_i \le 1,000,000


Output

Print the answer on the first line.


Subtask

# Score Condition
#13

N <= 3

#210

The answer is less than or equal to 2.

#320

When the condition is satisfied by changing the minimum number of cards, it is guaranteed that there exists a case where the difference between the numbers written on adjacent cards is 100 or less.

#467

No additional constraints.


Example #1

4

1 2 2 4
1

Example #2

5

6 3 3 1 -1
2


Source

KOI 2차 2022 초2/중1

You must sign in to write code.