Shortest Odd Sum Subsequence

You are given a sequence of integers. Your task is to find the length of the shortest subsequence of the given sequence such that the sum of its elements is an odd number. A subsequence is a sequence that can be derived from the given sequence by deleting some or no elements without changing the order of the remaining elements.

If there exists an odd number in the sequence, then the shortest subsequence is simply that one element (with length 1). Otherwise, if all numbers are even (or if the sequence is empty), output -1.

Formally, if we let \(a_1, a_2, \ldots, a_n\) be the sequence, find the minimum \(k\) (with \(1 \le k \le n\)) such that there exists indices \(i_1 < i_2 < \ldots < i_k\) with \[ a_{i_1} + a_{i_2} + \cdots + a_{i_k} \equiv 1 \pmod{2}. \] If no such subsequence exists, output -1.

inputFormat

The first line of input contains an integer n representing the number of elements in the sequence.

The second line contains n space-separated integers denoting the sequence.

outputFormat

Output a single integer representing the length of the shortest subsequence whose sum is odd. If no such subsequence exists, output -1.

## sample

4
2 4 6 8

-1

</p>