Тестування #27

Тестування

2 секунды
256 мегабайт
Very easy

Антончик вирішив пройти тестування. На вхід у тесті задається послідовність цілих чисел, а Антончику необхідно знайти зайве — число, яке відрізняється від всіх інших по парності. Допоможіть геройчику: знайдіть позицію числа з послідовності яке є зайвим.

Input

Перший рядок містить одне ціле число (3\le n\le 10^5) — довжина послідовності.

Другий рядок містить цілих чисел a_1, a_2, \dots, a_n (1\le a_i\le 10^5) — елементи послідовності.

Гарантується, що рівно одне з чисел є зайвим.

Output

Виведіть одне ціле число — позицію зайвого числа у послідовності. Числа послідовності нумеруються від до .

Examples

Example 1

Loading
Loading

Example 2

Loading
Loading

Note

У першому прикладі усі числа є парними, крім числа , оскільки воно третє, то потрібно вивести .

У другому прикладі усі числа непарні, крім , оскільки воно друге, то потрібно вивести .

Scoring

Рішення, які правильно працюватимуть при n\le 100, набиратимуть не менше балів.