В ряд выложено $N$ карт. Для удобства назовем самую левую карту картой 1, следующую за ней — картой 2, . . ., самую правую карту — картой $N$.

На каждой из $N$ карт написано одно целое число. Обозначим число, написанное на $i$-й карте, как $x_i$.

Требуется изменить числа на некоторых из $N$ карт так, чтобы при проходе слева направо числа на картах равномерно возрастали, равномерно убывали или же все числа были равны.

Числа на картах можно изменять только на целые числа, при этом количество замен необходимо минимизировать.

Например, пусть даны карты, как показано на рисунке ниже.

В этом случае, если изменить число на 3-й карте на 3, числа будут увеличиваться на 1, как показано ниже, а количество карт с измененными числами составит 1.

Также можно сделать так, чтобы на всех картах было написано число 2, как показано ниже. В этом случае количество карт с измененными числами составит 2.

Даны числа, написанные на картах по порядку от самой левой до самой правой. Найдите минимальное количество карт, числа на которых нужно изменить, чтобы удовлетворить условию.

Ограничения

• $2 \le N \le 500$
• Для всех $1 \le i \le N$ выполняется $-1\ 000\ 000 \le x_i \le 1\ 000\ 000$

Подзадачи

1. (3 балла) $N \le 3$.
2. (10 баллов) Ответ не превосходит 2.
3. (20 баллов) Гарантируется существование способа удовлетворить условию с минимальным количеством замен, при котором разность между числами на соседних картах не превышает 100.
4. (67 баллов) Без дополнительных ограничений.

Входные данные

В первой строке задано количество карт $N$.

Во второй строке через пробел по порядку заданы числа $x_i$, написанные на картах.

Выходные данные

В первой строке выведите ответ.

Примеры

Примеры

Входные данные 1

4
1 2 2 4

Выходные данные 1

1

Примеры

Входные данные 2

5
6 3 3 1 -1

Выходные данные 2

2