아니면 장난!

바이토카에는 다른 나라에서는 볼 수 없는 풍습이 있다. 초가을이 되면 아이들이 무서운 분장을 하고 집집마다 돌아다니며 주민들에게서 사탕을 받는다.

바이테크와 비토시아도 사탕을 모으러 나갈 계획이다. 두 사람은 한쪽에 집이 N채 늘어선 매우 긴 거리에 산다. 집에는 1번부터 N번까지 차례로 번호가 붙어 있다. 두 사람은 이 거리에 와 본 적이 있어서, 각 i = 1, 2, ..., N에 대해 i번째 집을 방문하면 정확히 $C_i$개의 사탕을 받는다는 것을 알고 있다.

매년 마지막 사탕 한 개를 두고 다투었기 때문에, 이번에는 반드시 사탕을 짝수 개 모으기로 했다. 계획은 두 집 번호 L과 R을 고른 뒤, L, L+1, ..., R-1, R번 집을 모두 방문하는 것이다. 이렇게 하면 정확히 $C_L + C_{L+1} + \ldots + C_{R-1} + C_R$개의 사탕을 모은다.

바이테크와 비토시아가 사탕을 짝수 개 모을 수 있도록 집 번호 L과 R을 고르는 방법은 몇 가지인가?

첫째 줄에 거리의 집 개수를 나타내는 정수 N ($1 \le N \le 1000000$)이 주어진다. 둘째 줄에는 N개의 정수 $C_1, C_2, \ldots, C_N$ ($1 \le C_i \le 10^9$)이 주어지며, $C_i$는 i번째 집에서 받을 수 있는 사탕의 개수이다.

아이들이 사탕을 짝수 개 모을 수 있는 집 번호 쌍 (L, R)의 개수를 한 줄에 출력한다.