0과 1 탐구

신비로운 이진 세계에 들어와 있습니다. 이곳에는 $N$개의 이진수로 이루어진 배열이 여러분의 조사를 기다리고 있습니다. 각 숫자는 0 또는 1이며, 이들이 모여 독특한 패턴을 만듭니다. 여러분의 임무는 1의 개수가 홀수인 부분 배열의 개수를 구하는 것입니다.

배열은 $b_1, b_2, \ldots, b_N$입니다. 부분 배열은 연속된 원소로 이루어진 구간입니다. 예를 들어 $[b_1, b_2, b_3]$의 부분 배열은 $[b_1]$, $[b_2]$, $[b_3]$, $[b_1, b_2]$, $[b_2, b_3]$, $[b_1, b_2, b_3]$입니다. 1의 개수가 홀수인 부분 배열의 개수를 구하세요. 답은 32비트 정수 범위를 넘을 수 있습니다.

첫째 줄에 이진 수열의 길이 $N$($1 \le N \le 10^5$)이 주어집니다.

둘째 줄에 $N$개의 이진수 $b_1, b_2, \ldots, b_N$($b_i \in \{0, 1\}$)이 주어집니다.

1의 개수가 홀수인 부분 배열의 개수를 한 줄에 출력합니다.