¿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 \leq N \leq 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 \leq 10~.
• En casos de prueba por valor del ~60\%~ de los puntos totales, se tendrá que ~N \leq 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\} \rightarrow \{3, 3\}~

2. ~\{1, 2, 4, 6, 1\} \rightarrow \{1, 6, 6, 1\}~

3. ~\{1, 4, 3, 2\} \rightarrow \{5, 3, 2\} \rightarrow \{5, 5\}~