Антончик вирішив пройти тестування. На вхід у тесті задається послідовність цілих чисел, а Антончику необхідно знайти зайве — число, яке відрізняється від всіх інших по парності. Допоможіть геройчику: знайдіть позицію числа з послідовності яке є зайвим.
Перший рядок містить одне ціле число n (3≤n≤105) — довжина послідовності.
Другий рядок містить n цілих чисел a1,a2,…,an (1≤ai≤105) — елементи послідовності.
Гарантується, що рівно одне з чисел є зайвим.
Виведіть одне ціле число — позицію зайвого числа у послідовності. Числа послідовності нумеруються від 1 до n.
У першому прикладі усі числа є парними, крім числа 7, оскільки воно третє, то потрібно вивести 3.
У другому прикладі усі числа непарні, крім 2, оскільки воно друге, то потрібно вивести 2.
Рішення, які правильно працюватимуть при n≤100, набиратимуть не менше 50% балів.