IQ test

Source: Codeforces

Version: Phuoc Hung OJ Extended

Problem

Among $n$ positive integers, exactly one differs from all the others in parity: either one is odd and all others are even, or one is even and all others are odd.

Print the 1-based position of that element.

Input

• Line 1: integer $n$.
• Line 2: $n$ integers.

Output

Print the 1-based position of the parity outlier.

Subtask

Subtask 1 (100 points): $3\le n\le100$; $1\le a_i\le100$; exactly one element differs in parity.

Example

Input

5
2 4 7 8 10

Output

3

Explanation

Only $7$ is odd, and it is at position $3$.