Descripción

El dígito de control de un número natural x se obtiene de la siguiente manera:

• si el número ~x~ tiene una sola cifra, entonces la cifra de control de ~x~ es igual a \(𝑥\);
• si el número ~x~ tiene al menos dos dígitos, se calcula la suma de los dígitos de x (denominada ~s~); el dígito de control de ~x~ será igual al dígito de control de ~s~.

Por ejemplo, el dígito de control del número ~175~ es igual al dígito de control del número ~13~ (~1 + 7 + 5~), que es igual a ~4~ (~1 + 3~).

Sea \(𝑥_1, 𝑥_2, ... , x_N\) una cadena de ~N~ números naturales. Dos posiciones ~i~ y ~j~ con \(1 \le i \le j \le 𝑁\) definen la secuencia [\(𝑖\), ~j~] que contendrá los números \(𝑥_i, 𝑥_{i+1}, ... , 𝑥_j\).

Una secuencia [\(𝑖\), ~j~] con la propiedad de que la suma de todos los elementos de la secuencia tiene dígito de control igual a ~9~ la denominamos secv9!.

Tarea

Escribir un programa que, conociendo \(𝑁\) el número de elementos de la cadena, \(x_1, 𝑥_2, ..., 𝑥_N\) elementos en la cadena, resolver los dos requisitos siguientes:

1. mostrar la longitud máxima de una secuencia secv9;
2. mostrar el número de secuencias secv9 en la cadena.

Entrada

La entrada contiene en la primera línea dos números naturales C y 𝑁 que representan el requisito a resolver (1 ó 2) y la longitud de la cadena. La siguiente línea contiene N números naturales \(𝑥_1, 𝑥_2, ..., 𝑥_N\) separados por un espacio cada uno, que representan los elementos de la cadena.

Salida

La salida contendrá en la primera línea un único número natural, que representa la respuesta al requisito ~C~ del archivo de entrada.

Restricciones

• ~1 \le N \le 1 000 000~
• \(0 \le 𝑥_i \le 1 000\), para cualquier \(1 \le i \le 𝑁\).
• Se garantiza para todos los datos de prueba que existe al menos una secuencia secv9

Subtareas

1. 8 puntos, si C = 1, para 1 ≤ N ≤ 1000

2. 10 puntos, si C = 1, para 1001 ≤ N ≤ 5 000

3. 22 puntos, si C = 1, para 5001 ≤ N ≤ 1 000 000

4. 12 puntos, si C = 2, para 1 ≤ N ≤ 1000

5. 15 puntos, si C = 2, para 1001 ≤ N ≤ 5 000

6. 33 puntos, si C = 2, para 5001 ≤ N ≤ 1 000 000

Ejemplos de Entrada y Salida

Ejemplo de Entrada #1

1 7
1 7 6 1 11 5 9

Ejemplo de Salida #1

3

Explicación

Hay dos secuencias secv9 en la cadena dada:

• la secuencia [3, 5], formada por los números 6, 1 y 11, tiene la suma de términos 18 = 6 + 1 + 11, por lo que el dígito de control es 9;
• la secuencia [7, 7], formada por el número 9, tiene la suma de términos 9, por lo que el dígito de control es 9. La longitud máxima de una secuencia secv9 es 3.

Ejemplo de Entrada #2

2 7
1 7 6 1 11 5 9

Ejemplo de Salida #2

2

Explicación

Hay dos secuencias secv9 en la cadena: [3, 5] y [7, 7].