== include(page="template/taskheader" task_id="valentin") ==

Valentin şi Valentina sunt gemeni. De ziua lor au primit de la părinţi un şir format din n numere întregi. Valentin a hotărât să păstreze doar câteva elemente ale şirului, astfel ca suma acestora să fie maximă şi mai mult de atât, să fie un număr par, pentru că, fiind un frate bun, doreşte să dea jumătate din sumă Valentinei.

Valentin şi Valentina sunt gemeni. De ziua lor au primit de la părinţi un şir format din {**n**} numere întregi. Valentin a hotărât să păstreze doar câteva elemente ale şirului, astfel ca suma acestora să fie {**maximă**} şi mai mult de atât, să fie un număr {**par**}, pentru că, fiind un frate bun, doreşte să dea jumătate din sumă Valentinei.

	Concentrându-se asupra problemei, el vrea să primească răspuns la două întrebări:
1.	Ce valoare are suma maximă pară unui subşir?

h2. Date de intrare

Fişierul de intrare $valentin.in$ conţine pe prima linie un număr natural v. Pentru toate testele de intrare, numărul v poate avea doar valoarea 1 sau 2.

Fişierul de intrare $valentin.in$ conţine pe prima linie un număr natural {**v**}. Pentru toate testele de intrare, numărul {**v**} poate avea doar valoarea {**1**} sau {**2**}.

A doua linie a fişierului conţine numărul natural n. Următoarea linie conţine cele n elemente ale şirului, numere întregi separate prin spaţii.

A doua linie a fişierului conţine numărul natural {**n**}. Următoarea linie conţine cele {**n**} elemente ale şirului, numere întregi separate prin spaţii.

h2. Date de ieşire

Dacă valoarea lui v este 1, se va rezolva numai punctul 1 din cerinţă.

Dacă valoarea lui {**v**} este {**1**}, se va rezolva numai punctul {**1**} din cerinţă.

În acest caz în fişierul de ieşire $valentin.out$ se va scrie un singur număr întreg ce reprezintă valoarea maximă a sumei pare a unui subşir.

Dacă valoarea lui v este 2, se va rezolva numai punctul 2 din cerinţă.

Dacă valoarea lui {**v**} este {**2**}, se va rezolva numai punctul {**2**} din cerinţă.

În acest caz, în fişierul de ieşire $valentin.out$ se va scrie un singur număr natural ce reprezintă numărul subşirurilor de sumă maximă pară.
h2. Restricţii

* 1 ≤ n ≤ 600 000;

* 1 ≤ {**n**} ≤ 600 000;

* -1 000 000 000 ≤ elementele şirului ≤ 1 000 000 000;
* suma maximă poate fi şi negativă;
* un subşir conţine cel puţin un element;
* două subşiruri se consideră distincte dacă diferă prin cel puţin o poziţie de element;
* pentru toate testele rezultatele se vor încadra în tipul long long (C/C++), respectiv int64 (Pascal) ;

* pentru 50% din teste valorarea lui v=1, alte pentru alte 50% din teste valoarea lui v=2;
* pentru 30% din teste valoarea lui n≤21
* pentru 45% din teste valoarea lui n≤1000
* pentru 60% din teste valoarea lui n≤50000

* pentru 50% din teste valorarea lui v = 1, alte pentru alte 50% din teste valoarea lui v = 2;
* pentru 30% din teste valoarea lui n ≤ 21
* pentru 45% din teste valoarea lui n ≤ 1000
* pentru 60% din teste valoarea lui n ≤ 50000

h2. Exemplu

| 5
| v=2, se rezolvă a doua cerinţă, adică:
avem 5 subşiruri cu suma maximă pară:

1. (a1, a2)                →   3-3=12

1. (a1, a2)                →   3-3=0

2. (a1, a2, a3)           →   3-3+0=0
3. (a1, a3, a4)           →   3+0-3=0
4. (a1, a4)                →   3-3=0