26755번 - ... albo psikus! 다국어

W Bajtocji panuje pewna tradycja, nieznana w innych zakątkach świata – na początku jesieni dzieci przebierają się w straszne kostiumy i chodzą od domu do domu, zbierając cukierki od mieszkańców.

Bajtek i Bitosia także planują wybrać się na zbieranie cukierków. Mieszkają oni przy bardzo długiej ulicy, która zawiera N domów mieszczących się po tej samej stronie drogi i ponumerowanych kolejno od 1 do N. Odwiedzali już tę ulicę wcześniej i wiedzą, dla każdego i = 1,2,...,N, że gdy odwiedzą i-ty dom, dostaną dokładnie Ci cukierków.

Jako że co roku wybuchały między nimi kłótnie o ostatniego cukierka, Bajtek i Bitosia postawili tym razem koniecznie zebrać parzystą liczbę cukierków. Ich planowana strategia to wybrać pewne dwa numery domów L i R, po czym odwiedzić wszystkie domy pomiędzy nimi, czyli L, L +1, ..., R−1, R. W ten sposób zbiorą dokładnie C_L +C_L+1 +...+ C_R−1 +C_R. cukierków.

Na ile różnych sposobów Bajtek i Bitosia mogą wybrać domy L i R tak aby zebrać parzystą liczbę cukierków?

W pierwszym wierszu wejścia dana jest liczba N (1 ≤ N ≤ 1 000 000), oznaczająca liczbę domów przy ulicy. W kolejnym wierszu dane jest N liczb C₁, C₂, ..., C_N (1 ≤ C_i ≤ 10⁹ dla 1 ≤ i ≤ N), gdzie C_i oznacza liczbę cukierków, które dzieci mogą zebrać odwiedzając dom o numerze i.

Wypisz jeden wiersz, zawierający liczbę możliwych par numerów domów (L,R), dla których dzieci zbiorą parzystą liczbę cukierków.