За умовою рівно одне число відрізняється за парністю від усіх інших. Отже, або в послідовності рівно одне непарне число, або рівно одне парне.
Звідси простий розв'язок у два проходи. Спочатку порахуємо кількість парних чисел та кількість непарних . Оскільки n \ge 3, рівно одна з цих величин дорівнює одиниці — саме вона і вказує на потрібну парність.
Другим проходом знайдемо позицію єдиного числа з цією парністю і виведемо її. Нумерація в задачі починається з одиниці, тому до індексу масиву треба додати .
Складність — , що з запасом вкладається в обмеження n \le 10^5. Зберігати всю послідовність не обов'язково: достатньо запам'ятати кількості чисел кожної парності та позиції першого парного і першого непарного.