secvente

Se consideră un șir cu $N$ elemente numere întregi. Definim următoarele noțiuni:

• secvență în șir = elemente situate pe poziții consecutive în șir
• lungimea unei secvențe = numărul de elemente care o formează
• suma unei secvențe = suma elementelor care o formează
• secvența nebanală = secvența de lungime cel puțin egală cu $2$
• N-secvență = secvență a cărei sumă este divizibilă cu $N$ (secvența poate fi și banală)
• N-secvență nebanală = secvență nebanală a cărei sumă este divizibilă cu $N$.

Cerință

Scrieți un program care să citească numărul natural $N$ și apoi șirul de $N$ elemente. Programul determină:

1. numărul de $N$-secvențe nebanale, din șir;
2. cea mai mare lungime a unei $N$-secvențe din șir;
3. cea mai mare sumă a unei $N$-secvențe din șir.

Date de intrare

Fișierul de intrare secvente.in conține pe prima linie numere naturale $C$ și $N$ separate printr-un singur spațiu. $C$ reprezentând cerința care trebuie rezolvată ($1, 2$ sau $3$).

Date de ieșire

Fișierul secvente.out va conține pe prima linie un număr natural reprezentând:

dacă $C = 1$, numărul de N-secvențe nebanale din șir (răspunsul la cerința $1$);
dacă $C = 2$, cea mai mare lungime a unei N-secvențe din șir (răspunsul la cerința $2$);
dacă $C = 3$, cea mai mare sumă a unei N-secvențe din șir (răspunsul la cerința $3$).

Restricții și precizări

• $2 \leq N \leq 100 \ 000$
• elementele șirului sunt numere întregi din interval închis $[-10^9, 10^9]$
• în șirul de numere dat există cel puțin o N-secvență a cărei sumă este un număr natural
• numărul întreg negativ $X$ este divizibil cu numărul natural nenul $N$ dacă restul împărțirii modulului lui $X$ la $N$ este $0$ (de exemplu, $X=-30$ este divizibil cu $N=6$, iar $X=-45$ nu este divizibil cu $N=6$)
• Pentru pentru fiecare dintre cerințele $1$ și $2$ se acordă $30$p, iar pentru cerința $3$ se acordă $40$p.

Exemplul 1

secvente.in

1 10
-9 -3 4 -10 -1 -16 18 18 -10 50

secvente.out

8

Explicație

Se rezolvă cerința $1$. Șirul are $N=10$ elemente întregi: $-9, -3, 4, -10, -1, -16, 18, 18, -10, 50$.

Cele N-secvențe nebanale sunt ( $-3, 4$ , $-10, -1$ ) , ($-16, 18, 18$), ($-10, 50$), ($-16, 18$ , $18, -10$), ($-16, 18$ , $18, -10, 50$), $(-3, 4, -10$ , $-1, -16, 18, 18$), ($-3, 4, -10$ , $-1, -16, 18$ , $18, -10$), ($-3, 4, -10$ , $-1, -16, 18$ , $18, -10, 50$) .

Exemplul 2

secvente.in

2 10
-9 -3 4 -10 -1 -16 18 18 -10 50

secvente.out

9

Explicație

Se rezolvă cerința $2$. Șirul are N=10 elemente întregi: $-9, -3, 4, -10$ , $-1, -16, 18$ , $18, -10, 50$.

Cea mai lungă dintre aceste secvențe este N-secvența ($-3, 4,-10,-1$ , $-16,18,18$ , $-10,50$). Lungimea acestei secvențe este $9$.

secvente.in

3 10
-9 -3 4 -10 -1 -16 18 18 -10 50

secvente.out

60

Explicație

Se rezolvă cerința $3$. Șirul are N=10 elemente întregi: $-9, -3, 4, -10$ , $-1, -16, 18$ , $18, -10, 50$.

Suma maximă a unei secvente este $60$ (suma N-secvenței: $-16,18,18$ , $-10,50$).