¿Los gansos ven a Dios? ¿O fue una rata lo que vi? No importa si son gansos o ratas, esto es solo una introducción innecesaria para mostrar el amor de Mislav por los palíndromos. Ayúdalo a resolver la siguiente tarea!

Sea ~A~ un arreglo de ~N~ números enteros. Decimos que ~A~ es palindrómico si para cada ~i~ tiene ~A [i] = A [N-i + 1]~, donde ~A [i]~ representa el ~i~-ésimo elemento del arreglo ~A~, y el índice del primer elemento en el arreglo es ~1~.

Mislav puede modificar el arreglo de la siguiente manera: en un solo movimiento, elige dos elementos adyacentes de esa matriz y los reemplaza con su suma. Observe que la cantidad de elementos en el arreglo se reducirá en 1 después de cada movimiento. Mislav quiere saber cuál es el número mínimo de movimientos que debe realizar para que la matriz original se vuelva palindrómica.

Entrada

La primera línea de entrada contiene el entero ~N (1 \le N \le 10^6)~ que representa el número de elementos de la matriz.

La siguiente línea contiene ~N~ números enteros positivos separados por espacios que representan los elementos en la matriz de Mislav. Los números en la entrada serán como máximo ~10^9~.

Salida

Genere el número mínimo de movimientos necesarios para transformar el arreglo original en uno palindrómico, dadas las reglas del problema.

Puntuación

En casos de prueba que valgan el ~30\%~ del total de puntos, se tendrá que ~N \le 10~.

En casos de prueba por valor del ~60\%~ de los puntos totales, se tendrá que ~N \le 1000~.

Ejemplos

Ejemplo de entrada 1

3
1 2 3

Ejemplo de salida 1

1

Ejemplo de entrada 2

5
1 2 4 6 1

Ejemplo de salida 2

1

Ejemplo de entrada 3

4
1 4 3 2

Ejemplo de salida 3

2

Aclaración de los ejemplos:

1. ~\{1, 2, 3\} -> \{3, 3\}~

2. ~\{1, 2, 4, 6, 1\} -> \{1, 6, 6, 1\}~

3. ~\{1, 4, 3, 2\} -> \{5, 3, 2\} -> \{5, 5\}~