Hay $N$ cartas dispuestas en una fila. Por conveniencia, llamemos a la carta más a la izquierda la carta 1, a la siguiente la carta 2, ..., y a la carta más a la derecha la carta $N$.

Cada una de las $N$ cartas tiene un número entero escrito en ella. Sea $x_i$ el número escrito en la carta $i$.

Queremos cambiar adecuadamente los números escritos en algunas de las $N$ cartas de modo que, de izquierda a derecha, los números escritos en las cartas aumenten a un ritmo constante, disminuyan a un ritmo constante, o sean todos iguales (es decir, formen una progresión aritmética).

Al cambiar los números escritos en las cartas, solo se pueden cambiar a valores enteros, y se debe minimizar la cantidad de cambios realizados.

Por ejemplo, supongamos que las cartas se dan como en la figura de abajo.

En este caso, si cambiamos el número escrito en la carta 3 por 3, podemos hacer que aumenten de 1 en 1 como se muestra abajo, y la cantidad de cartas cuyos números se cambiaron es 1.

También es posible hacer que los números escritos en todas las cartas sean 2, como se muestra a continuación. En este caso, la cantidad de cartas cuyos números se cambiaron es 2.

Dados en orden los números escritos en cada carta, desde la carta más a la izquierda hasta la más a la derecha, determina la cantidad mínima de cartas que se deben cambiar para satisfacer la condición.

Restricciones

• $2 \le N \le 500$
• Para todo $1 \le i \le N$, $-1\ 000\ 000 \le x_i \le 1\ 000\ 000$

Subtareas

1. (3 puntos) $N \le 3$.
2. (10 puntos) La respuesta es como máximo 2.
3. (20 puntos) Se garantiza que existe una manera de satisfacer la condición cambiando la cantidad mínima de cartas tal que la diferencia entre los números de cartas adyacentes sea como máximo 100.
4. (67 puntos) Sin restricciones adicionales.

Entrada

La primera línea contiene la cantidad de cartas $N$.

La segunda línea contiene los números $x_i$ escritos en cada carta, en orden y separados por espacios.

Salida

Imprime la respuesta en la primera línea.

Ejemplos

Entrada 1

4
1 2 2 4

Salida 1

1

Ejemplos

Entrada 2

5
6 3 3 1 -1

Salida 2

2