secv9

Cifra de control a unui număr natural $x$ se obține astfel:

• dacă numărul $x$ are o singură cifră, atunci cifra de control a lui $x$ este egală cu $x$;
• dacă numărul $x$ are cel puțin două cifre, atunci se calculează suma cifrelor lui $x$ (să o notăm cu $s$); cifra de control a lui $x$ va fi egală cu cifra de control a lui $s$.

De exemplu, cifra de control a numărului $175$ este egală cu cifra de control a numărului $13 (1 + 7 + 5)$, care este egală cu $4 (1 + 3)$.
Fie $x_1, x_2, \dots, x_N$ un șir de $N$ numere naturale. Două poziții $i$ și $j$, cu $1 \leq i \leq j \leq N$, definesc secvența $[i, j]$ care va conține numerele $x_i, x_{i+1}, \dots, x_j$.
O secvență $[i, j]$ cu proprietatea că suma tuturor elementelor din secvență are cifra de control egală cu $9$ o vom denumi secv9.

Cerință

Scrieţi un program care, cunoscând $N$, numărul de elemente din șir, respectiv $x_1, x_2, \dots, x_N$, elementele din șir, rezolvă următoarele două cerințe:

1. afișează lungimea maximă a unei secvențe secv9;
2. afișează numărul de secvențe secv9 din șir.

Date de intrare

Fişierul de intrare secv9.in conține pe prima linie două numere naturale $C$ și $N$, reprezentând cerința care trebuie rezolvată ($1$ sau $2$), respectiv lungimea șirului. Următoarea linie conține $N$ numere naturale $x_1, x_2, \dots, x_N$, separate prin câte un spațiu, reprezentând elementele din șir.

Date de ieșire

Fişierul de ieşire secv9.out va conţine pe prima linie un singur număr natural, reprezentând răspunsul la cerința $C$ din fișierul de intrare.

Restricții și precizări

• $1 \leq N \leq 1 \ 000 \ 000$
• $0 \leq x_i \leq 1 \ 000$, pentru oricare $1 \leq i \leq N$.
• Se garantează pentru toate datele de test că există cel puțin o secvență secv9.

Exemplul 1

secv9.in

1 7
1 7 6 1 11 5 9

secv9.out

3

Explicație

Sunt două secvențe secv9 în șirul dat:

• secvența $[3,5]$, alcătuită din numerele $6, 1$ și $11$, are suma termenilor $18=6+1+11$, deci cifra de control este $9$;
• secvența $[7,7]$, alcătuită din numărul $9$, are suma termenilor $9$, deci cifra de control este $9$.

Lungimea maximă a unei secvențe secv9 este 3.

Exemplul 2

secv9.in

2 7
1 7 6 1 11 5 9

secv9.out

2

Explicație

Sunt două secvențe secv9 în șir: $[3,5]$ și $[7,7]$.