Descripción

Maullín logra llegar a la puerta, pero esta tiene un candado con una combinación. En todo el desorden, encuentra la forma para obtener la combinación.

La puerta tiene una secuencia de números del 1 al 9, pero Maullín tiene miedo por lo que puede encontrar cuando salga. Tal vez lo mejor sea quedarse donde está y vivir ahí mismo. Él ya sabe qué combinación es, pero quiere prolongar más tiempo en lo que se mentaliza para salir, así que para relajarse quiere ver cuántas combinaciones hay que puedan abrir la puerta.

Una combinación es válida para abrir la puerta si es un subarreglo que tiene un promedio entero.
Él quiere saber cuántos subarreglos tienen un promedio entero, es decir, cuántas combinaciones válidas hay.

Ayuda al gato sin identidad.

Entrada

Un entero \(n\) el tamaño de la secuencia.
Seguido de \(n\) números enteros \(a_1, a_2, ..., a_n\).

Salida

Un solo entero, la cantidad de subarreglos cuyo promedio es entero.

Ejemplo

Entrada

5
1 2 3 4 5

Salida

9

Explicación
Los subarreglos de la secuencia son:

Subarreglos de longitud \(1\): \([1], [2], [3], [4], [5]\) (todos los promedios son enteros).

Subarreglos de longitud \(2\): \([1, 2], [2, 3], [3, 4], [4, 5]\) (los promedios son \(1.5, 2.5, 3.5, 4.5\), respectivamente; ninguno es entero).

Subarreglos de longitud \(3\): \([1, 2, 3], [2, 3, 4], [3, 4, 5]\) (los promedios son \(2, 3, 4\), todos son enteros).

Subarreglos de longitud \(4\): \([1, 2, 3, 4], [2, 3, 4, 5]\) (los promedios son \(2.5, 3.5\), respectivamente; ninguno es entero).

Subarreglos de longitud \(5\): \([1, 2, 3, 4, 5]\) (el promedio es \(3\), es entero).

Así que hay \(9\) subarreglos con un promedio entero.

Límites

• \(1 \leq n \leq 300\)

• \(1 \leq a_i \leq 9\)