29994번 - Investigating Zeroes and Ones 다국어

문제

You find yourself in a mysterious binary world, where an array of N binary digits awaits your scrutiny. Each digit is either a zero or a one, creating a unique pattern across the landscape. Your quest is to uncover the hidden patterns of this binary realm by unraveling the significance of subarrays with an odd number of ones.

The array of digits is denoted as b₁, b₂, . . . , b_N. Your task is to embark on a journey to discover the enigmatic subarrays – segments of consecutive digits – and determine the count of subarrays that harbor an odd number of ones.

As you traverse this binary landscape, remember that a subarray is defined by its starting and ending digits. For instance, in the sequence [b₁, b₂, b₃], subarrays include [b₁], [b₂], [b₃], [b₁, b₂], [b₂, b₃], and [b₁, b₂, b₃].

Your mission is to design an algorithm that determines the total number of subarrays containing an odd number of ones within this binary sequence. Please don’t forget that the answer might not fit in a 32-bits integer.

입력

The first line contains an integer N (1 ≤ N ≤ 10⁵) representing the length of the binary sequence.

The second line contains N binary digits b₁, b₂, . . . , b_N (b_i ∈ {0, 1}) representing the elements of the sequence.

출력

Output a single line with an integer representing the count of subarrays in the sequence that hold an odd number of ones.

제한

힌트