Тестування

Input

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

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

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

Output

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

Examples

Example 1

Loading

Example 2

Loading

Note

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

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

Scoring

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