1. Идея

Нужно найти не само максимальное значение, а позицию его первого появления.

Самый простой способ: пройти по всем дорожкам слева направо, хранить текущее максимальное значение и номер дорожки, на которой оно встретилось впервые. Если встретили число строго больше текущего максимума, обновляем и максимум, и ответ. Если встретили равное значение, ничего не делаем — тогда сохранится первая позиция.

2. Наблюдения

• Нумерация в задаче начинается с 1, а не с 0.
• Если максимум встречается несколько раз, нужен именно первый индекс.
• Поэтому обновлять ответ надо только при условии a[i] > mx.
• Если писать a[i] >= mx, то ответ станет индексом последнего максимума, а это неверно.
• Так как n может быть до 2 * 10^5, нужен линейный алгоритм за один проход.

3. Алгоритм

1. Считываем n.
2. Считываем значения.
3. Берём первое значение как текущий максимум mx.
4. Запоминаем ответ ans = 1.
5. Идём по остальным элементам:
   • если очередное значение больше mx, то:
     • обновляем mx,
     • записываем текущий индекс в ans.
6. Выводим ans.

4. Почему это работает

После обработки первых k элементов будем поддерживать такой инвариант:

• mx — максимальное значение среди первых k элементов;
• ans — индекс первого вхождения этого максимума среди первых k элементов.

Почему это верно:

• Для первого элемента всё очевидно: максимум равен ему самому, а его индекс — 1.
• Пусть утверждение верно после обработки нескольких элементов.
• Рассмотрим следующий элемент:
  • если он меньше или равен mx, то максимум среди просмотренных элементов не меняется;
    • при равенстве первый индекс максимума тоже не меняется, потому что новое вхождение не первое;
  • если он больше mx, то теперь именно он является новым максимумом, и его индекс нужно записать в ответ.
• Значит, инвариант сохраняется на каждом шаге.

После обработки всех элементов ans будет индексом первого максимального элемента во всём массиве, что и требуется.

5. Сложность

• Время: O(n), потому что каждый элемент рассматривается один раз.
• Память:
  • для приведённого решения на C++ — O(1), так как числа обрабатываются по мере чтения;
  • для приведённого решения на Python — O(n), так как массив считывается целиком.

6. Код на C++17

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;

    long long x;
    cin >> x;

    long long mx = x;
    int ans = 1;

    for (int i = 2; i <= n; i++) {
        cin >> x;
        if (x > mx) {
            mx = x;
            ans = i;
        }
    }

    cout << ans << '\n';
    return 0;
}

7. Код на Python 3

n = int(input())
a = list(map(int, input().split()))

mx = a[0]
ans = 1

for i in range(1, n):
    if a[i] > mx:
        mx = a[i]
        ans = i + 1

print(ans)