Тестування

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

Input

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

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

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

Output

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

Examples

Note

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

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

Scoring

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