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

Poveste şi cerinţă...

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?
2.	Câte subşiruri distincte există cu suma maximă pară?

h2. Date de intrare

Fişierul de intrare $valentin.in$ ...

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.
 

h2. Date de ieşire

În fişierul de ieşire $valentin.out$ ...

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ţă.
Î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 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

h2. Exemplu

table(example). |_. valentin.in |_. valentin.out |
| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.
|
 
h3. Explicaţie
 
...

table(example). |_. valentin.in |_. valentin.out |_. Explicatie |
| 1
4
3 -3 0 -3
| 0
| v=1, se rezolvă prima cerinţă, adică:
suma maximă pară a unui subşir este 0.
|
 
table(example). |_. valentin.in |_. valentin.out |_. Explicatie |
| 2
4
3 -3 0 -3
| 5
| v=2, se rezolvă a doua cerinţă, adică:
avem 5 subşiruri cu suma maximă pară:
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
5. (a3)                     →   0=0
|

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