secv

Se consideră două numerele naturale $K$ și $S$ și un șir de $N$ numere naturale $a_1$, $a_2$, $\dots$, $a_N$. O secvenţă de lungime $K$ este un subşir format din $K$ elemente aflate pe poziţii consecutive în şir: $a_i$, $a_{i+1}$, $\dots$, $a_{i+k-1}$. Parcurgând șirul de la stânga la dreapta, începând cu primul element, se elimină prima secvență de lungime $K$, cu suma elementelor strict mai mare decât numărul $S$. În urma ștergerii șirul va avea $N - K$ elemente: $a_1$, $a_2$, $\dots$, $a_{N-K}$. Operația de ștergere continuă după aceleași reguli până când nu mai există secvențe care pot fi eliminate.

Cerinţe

Să se scrie un program care citind numerele $N$, $K$, $S$ și cele $N$ elemente din șir rezolvă cerințele:

1. Determină numărul secvențelor care se vor elimina respectând condiția din enunț.
2. Considerând că în șirul citit nu sunt posibile eliminări de secvențe conform condiției din enunț, programul determină numărul de elemente $a_i$ din șir cu proprietatea următoare: ștergerea lui $a_i$ conduce la obținerea unui șir în care se mai poate elimina cel puțin o secvență de $K$ elemente cu sumă strict mai mare ca $S$.

Date de intrare

Fișierul de intrare secv.in conţine pe prima linie un număr natural $P$; numărul $P$ poate avea doar valoarea $1$ sau valoarea $2$. A doua linie conține, în această ordine, separate prin câte un spațiu, numerele $N$, $K$ și $S$. A treia linie conține, în ordine elementele șirului, despărțite prin câte un spațiu.

Date de ieşire

Dacă valoarea lui $P$ este $1$, se va rezolva numai cerinta $1$. În acest caz, fişierul de ieşire secv.out va conține pe prima linie un număr natural reprezentând numărul secvențelor eliminate.
Dacă valoarea lui $P$ este $2$, se va rezolva numai cerinta $2$. În acest caz, fişierul de ieşire secv.out va conține pe prima linie un număr natural reprezentând numărul elementelor din șir care au proprietatea că ștergerea fiecăruia în parte ar genera un șir în care se mai pot elimina cel puțin o secvență de $K$ elemente cu sumă strict mai mare ca $S$.

Restricții și precizări

• $0 < K \leq N \leq 1 \ 000 \ 000$
• $0 < S \leq 1 \ 000 \ 000 \ 000$
• $0 \leq a_1, a_2, \dots, a_N \leq 1 \ 000$
• Pentru rezolvarea corectă a primei cerinţe se acordă $40$ de puncte iar pentru rezolvarea corectă a celei de a doua cerințe se acordă $60$ de puncte

Exemplul 1

secv.in

1
14 3 7
1 2 1 3 1 4 5 2 1 4 1 8 2 3

secv.out

3

Explicație

Prima secvență de sumă strict mai mare decât $7$ începe de pe poziția $4$ și este formată din elementele $3 \ 1 \ 4$; după eliminarea ei șirul devine:
$1$, $2$, $1$, $5$, $2$, $1$, $4$, $1$, $8$, $2$, $3$.
A doua secvență ce va fi ștearsă începe de pe poziția $2$ și este formată din $2 \ 1 \ 5$; după eliminarea ei șirul devine: $1$, $2$, $1$, $4$, $1$, $8$, $2$, $3$
A treia secvență ce va fi ștearsă începe de pe poziția $4$ și este formată din elementele $4 \ 1 \ 8$; după eliminarea ei șirul devine: $1$, $2$, $1$, $2$, $3$ și nu mai conține nici o secvență de $3$ elemente alăturate de sumă mai mare decât $7$.

Exemplul 2

secv.in

2
9 7 18
3 3 2 1 3 3 3 3 1

secv.out

2

Explicație

Două elemente au această proprietate. Dacă eliminăm elementul al treilea, de valoare $2$, se poate obține șirul $3$, $3$, $1$, $3$, $3$, $3$, $3$, $1$ care conține o secvență de $7$ elemente de sumă strict mai mare ca $18$, începând cu elementul de pe poziția $1$.
Dacă eliminăm elementul al patrulea, de valoare $1$, se poate obține șirul $3$, $3$, $2$, $3$, $3$, $3$, $3$, $1$ care conține o secvență de $7$ elemente de sumă strict mai mare ca $18$, începând cu elementul de pe poziția $1$.