Odd-Even Subarrays
/

## Algorithms, Dynamic Programming, Introduction to Dynamic Programming 1

Problem
Editorial
Analytics

You are given an array A of N positive integer values. A subarray of this array is called Odd-Even subarray if the number of odd integers in this subarray is equal to the number  of even integers in this subarray.

Find the number of Odd-Even subarrays for the given array.

Input Format:
The input consists of two lines.

First line denotes N - size of array.
Second line contains N space separated positive integers denoting the elements of array A.

Output Format:
Print a single integer, denoting the number of Odd-Even subarrays for the given array.

Constraints:

• $1 \leq N \leq 2 \times 10^5$
• $1 \leq A[i] \leq 10^9$

SAMPLE INPUT
4
1 2 1 2
SAMPLE OUTPUT
4
Explanation

Let $A[i..j]$ denotes the subarray of A starting at index i and ending at index j.

The four subarrays in which number of odd integers are equal to number of even integers are:

$A[1..2] = [1, 2]$ contains one odd and one even integer

$A[2..3] = [2, 1]$ contains one odd and one even integer

$A[3..4] = [1, 2]$ contains one odd and one even integer

$A[1..4] = [1, 2, 1, 2]$ contains two odd and two even integers

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB

## This Problem was Asked in

Initializing Code Editor...