Первый подход

Поддерживать две переменные для количества чётных и нечётных элементов. По этой информации можно найти нужную нам чётность, а затем ещё раз пробежаться по массиву и вывести нужное нам число (индекс числа).

Второй подход

Создать два массива для чётных и нечётных, в них будем хранить индексы чисел. Затем выведем первый элемент из меньшего массива.

Если использовать динамический массив, то я бы поступил следующем образом :

1. Создал два массива размера n.
2. Создал две дополнительные переменные, для поддерживания фактического размера.
3. Сравнил две переменные (из пункта 2)
4. Вывел первый элемент нужного массива

Третий подход

Подсчитать сумму индексов и количество чётных и нечётных чисел. Сравнить их и вывести существующую сумму, так как сумма из одного индекса является ответом.

Рекомендую реализовать каждый из вариантов решения и сдать задачу.