Odd Sum Subarray

Given an array of non-negative integers, determine whether there exists a contiguous subarray whose sum is an odd number. A contiguous subarray is defined as a sequence of consecutive elements in the array. Note that a single odd element is sufficient, as it forms a valid subarray with an odd sum.

The solution should work efficiently even for large arrays.

inputFormat

The first line contains an integer n (1 ≤ n ≤ 10⁵), representing the number of elements in the array.

The second line contains n space-separated non-negative integers, each less than 10⁹.

outputFormat

Print True if there exists at least one contiguous subarray with an odd sum; otherwise, print False.

5
2 4 6 8 5

True