Longest Even Sum Subarray

You are given an integer n and a sequence of n integers. Your task is to find the length of the longest contiguous subarray whose sum is even. A contiguous subarray is a sequence of consecutive elements from the original array.

The solution should efficiently process the array, ideally in linear time, by making use of prefix sum techniques and appropriate hash mapping. In mathematical terms, if the prefix sum up to index i is \(S_i = \sum_{j=0}^{i} a_j\), then a subarray from index l to r has an even sum if:

[ (S_r - S_{l-1}) \equiv 0 \pmod{2}. ]

Your program should read the input from standard input and output the result to standard output.

inputFormat

The first line of input contains a single integer n representing the number of elements in the sequence. The second line contains n space-separated integers, which constitute the sequence.

Example:

5
1 2 3 4 5

outputFormat

Output a single integer which is the length of the longest contiguous subarray with an even sum.

Example:

4

## sample

5
1 2 3 4 5

4