evaziune

Gigel, celebrul antreprenor din Brașov, cunoscut pentru afacerile sale complet legitime cu paleți euro și criptomonede, a uitat (din motive pe care avocatul său l-a sfătuit să nu le divulge) să-și plătească taxele timp de 7 ani consecutivi.

Într-o dimineață mohorâtă de ianuarie, un plic oficial cu antetul ANAF a aterizat în cutia poștală ruginită de la poarta vilei sale. Scrisoarea, redactată în limbajul inconfundabil al administrației publice, îl anunța că în maximum 30 de zile o echipă de inspectori va veni să-i verifice registrele contabile.

Gigel a intrat în panică.

Registrul său conținea $n$ tranzacții, fiecare reprezentată printr-un număr întreg $a_i$, unele pozitive, altele negative, altele supicios de rotunde. Știa cum funcționează inspecțiile: va trebui să prezinte inspectorului o subsecvență continuă din registru, iar acesta o va verifica folosind celebra Regulă de Aur a Contabilității Creative, învățată la masterul de evaziune fiscală de la ASE:

Cu alte cuvinte, fiecare tranzacție trebuie să fie exact diferența celor două tranzacții anterioare, o proprietate pe care doar registrele cu adevărat legitime o au.

Gigel nu poate modifica registrul (e deja înregistrat la Registrul Comerțului), dar poate alege ce porțiune să prezinte. Evident, vrea să prezinte cât mai multe tranzacții (să pară că a muncit din greu) dar fără să fie prins cu încălcări.

Disperat, Gigel și-a sunat cumnatul, Dorel, care lucra ca om de serviciu la sediul central ANAF din București. Dorel, în schimbul unui Audi A6 second-hand din Germania și a unei săptămâni la munte în Poiana Brașov, a acceptat să facă niște cercetări.

Trei zile mai târziu, Dorel l-a sunat înapoi.

• "Nea Gigele, am vorbit cu Maricica de la Resurse Umane. Zice că sunt trei tipuri de inspectori la ANAF. Fiecare are altă treabă cu regulile, dacă înțelegi ce zic..."
• "Spune, Dorele, spune!"
• "Păi... uite cum stă treaba..."

Inspectorul de tip 1 ($c = 1$) -"Incorruptibilul"

• "Primul tip e nasol rău, nea Gigele. Ăsta e proaspăt angajat, absolvent de Academia de Poliție, cu media $10$ și sufletul curat. Nu acceptă NIMIC."
• "Secvența pe care i-o arăți trebuie să respecte Regula de Aur PERFECT. O singură tranzacție care nu se potrivește și te trimite direct la pârnaie."

Gigel a înghițit în sec.

Inspectorul de Tip 2 ($c = 2$) - "Flexibilul"

• "Al doilea tip e mai bătrân, are 30 de ani în sistem. A văzut el multe."
• "Ăsta acceptă ca în secvența ta să existe maxim $k$ tranzacții care încalcă regula. Zice el că sunt 'erori de transcriere' și nu face caz. Dar dacă depășești $k$... pușcărie."
• "Și cum aflu cât e $k$?" întrebă Gigel.
• "Păi... Maricica zice că mai trebuie un televizor pentru cantina de la etajul 3. Samsung, 55 inch, Smart TV."
• "Făcut."

Inspectorul de Tip 3 ($c = 3$) - "Coruptibilul"

• "Al treilea tip, nea Gigele... ăsta e preferatul meu. Băiat de băiat. Îl cheamă Văsâi, joacă poker cu mine vinerea."
• "El acceptă încălcări ale regulii, DAR cu două condiții care trebuie respectate."
• "Ce condiții?"
• "Prima: numărul total de tranzacții care încalcă regula trebuie să fie maxim $k$."
• "A doua: pentru fiecare tranzacție $a_i$ care încalcă regula, calculează o penalitate:"

• "Suma penalităților trebuie să fie maxim $b$. Deci dacă ai prea multe încălcări, ești mort. Asta e mita, nea Gigele."
• "Înțeleg... deci trebuie să respect ambele condiții în același timp?"
• "Exact, nea Gigele. Maxim $k$ tranzacții greșite, iar suma devierilor lor maxim $b$. Depășești oricare din ele, pușcărie."
• "Și cum aflu $k$ și $b$?"
• "Maricica zice că mai trebuie un frigider pentru biroul ei și o excursie în Turcia, all-inclusive, 5 stele."
• "FĂCUT."

Dorel a închis telefonul. Gigel s-a așezat la birou, a deschis registrul, și a început să se gândească: care e cea mai lungă subsecvență continuă de tranzacții pe care o poate prezenta inspectorului, astfel încât să nu ajungă la pușcărie?

Tu, ca prieten bun al lui Gigel, trebuie să-l ajuți să găsească răspunsul.

Cerință

Se dă tipul inspectorului $c$ și șirul de $n$ tranzacții $a_1, a_2, \ldots, a_n$. Gigel alege o subsecvență continuă $[a_L, a_{L+1}, \ldots, a_R]$. Trebuie să determini lungimea maximă $R-L+1$ astfel încât subsecvența să fie acceptată.

Pentru o poziție $i$ (cu $L+2 \le i \le R$), regula așteptată este:

Condiția de acceptare depinde de $c$:

• Dacă $c = 1$: nu există abateri. Pentru toate $i \in [L+2, R]$ trebuie să fie adevărată regula.
• Dacă $c = 2$: se acceptă cel mult $k$ poziții $i \in [L+2, R]$ pentru care regula nu este adevărată.
• Dacă $c = 3$: se acceptă cel mult $k$ încălcări, iar pentru fiecare încălcare la poziția $i$ penalitatea este: $$p_i = |a_i - (a_{i-1} - a_{i-2})|.$$Subsecvența este acceptată dacă:
  • numărul încălcărilor $\le k$
  • suma penalităților încălcărilor $\sum p_i \le b$

Observație: orice subsecvență de lungime $1$ sau $2$ este considerată validă, deoarece regula se poate verifica doar de la al treilea element.

Date de intrare

Fișierul de intrare evaziune.in conține:

• Pe prima linie, două numere întregi $n$ și $c$, separate prin spațiu.
• Pe a doua linie, $n$ numere întregi $a_1, a_2, \ldots, a_n$, separate prin spațiu.
• Dacă $c = 2$: pe a treia linie se găsește numărul $k$.
• Dacă $c = 3$: pe a treia linie se găsesc numerele $k$ și $b$, separate prin spațiu.

Date de ieșire

Fișierul de ieșire evaziune.out va conține un singur număr întreg: lungimea maximă a subsecvenței valide.

Restricții și precizări

• $1 \leq n \leq 100 \ 000$;
• $c \in \{1, 2, 3\}$
• $|a_i| \leq 10^{9}$;
• $0 \leq k \leq n$;
• $0 \leq b \leq 10^{18}$;
• Orice subsecvență de lungime $1$ sau $2$ este considerată validă pentru toate tipurile de inspectori, deoarece Regula de Aur necesită cel puțin $3$ elemente pentru a putea fi verificată.

Exemplul 1

evaziune.in

7 1
1 2 1 -1 -2 -1 1

evaziune.out

7

Explicație

Inspectorul este de tip 1 (Incorruptibilul). Subsecvența $[1, 2, 1, -1, -2, -1, 1]$ (pozițiile 1-7) respectă perfect Regula de Aur:

• $a_3 = 1 = 2 - 1 = a_2 - a_1$ - valid
• $a_4 = -1 = 1 - 2 = a_3 - a_2$ - valid
• $a_5 = -2 = -1 - 1 = a_4 - a_3$ - valid
• $a_6 = -1 = -1 - -1 = a_5 - a_4$ - valid
• $a_7 = 1 = -1 - -2 = a_6 - a_5$ - valid

Exemplul 2

evaziune.in

7 2
1 2 1 -1 0 -1 1
2

evaziune.out

6

Explicație

Inspectorul este de tip 2 (Flexibilul) cu $k = 2$. Subsecvența $[1, 2, 1, -1, 0, -1]$ (pozițiile 1-6) conține exact 2 încălcări:

• $a_3 = 1 = 1$ $\rightarrow$ valid
• $a_4 = -1 = -1$ $\rightarrow$ valid
• $a_5 = 0$, așteptat $-1 - 1 = -2$ $\rightarrow$ invalid (încălcare #1)
• $a_6 = -1$, așteptat $0 - (-1) = 1$ $\rightarrow$ invalid (încălcare #2)

Deoarece avem exact $k = 2$ încălcări, subsecvența este validă.

Exemplul 3

evaziune.in

7 3
1 2 1 -1 0 -1 1
3 6

evaziune.out

7

Explicație

Inspectorul este de tip 3 (Coruptibilul) cu $k = 3$ și $b = 6$. Verificăm întreaga secvență:

• $a_3 = 1 = 1$ $\rightarrow$ valid
• $a_4 = -1 = -1$ $\rightarrow$ valid
• $a_5 = 0$, așteptat $-2$ $\rightarrow$ invalid (încălcare, penalitate $|0 - (-2)| = 2$)
• $a_6 = -1$, așteptat $1$ $\rightarrow$ invalid (încălcare, penalitate $|-1 - 1| = 2$)
• $a_7 = 1$, așteptat $-1$ $\rightarrow$ invalid (încălcare, penalitate $|1 - (-1)| = 2$)

Avem $3$ incalcari si suma penalitatilor este $2 + 2 + 2 = 6$. Ambele conditii sunt respectate, deci intreaga secventa este valida.