Идея

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

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

Наблюдения

1. Ответ состоит из двух частей:

   • самого большого значения;
   • его индекса, считая с 1.

2. Если максимальный элемент встречается несколько раз, нужен индекс первого такого элемента.

3. Поэтому условие обновления должно быть именно a[i] > mx, а не a[i] >= mx.

   • При > первое вхождение сохраняется.
   • При >= индекс бы перезаписывался, и получилось бы последнее вхождение, что неверно.

4. Ограничения большие, но здесь достаточно одного прохода по массиву.

Алгоритм

1. Считать n.
2. Считать массив из n чисел.
3. Принять первый элемент за текущий максимум:
   • mx = a[0]
   • idx = 1
4. Пройти по остальным элементам массива, начиная со второго:
   • если a[i] > mx, то:
     • обновить mx = a[i]
     • обновить idx = i + 1, потому что индексация в ответе с 1
5. Вывести mx и idx.

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

Докажем, что после обработки всех элементов:

• mx — это максимальный элемент массива;
• idx — индекс его первого появления.

Сначала после чтения первого элемента:

• mx равен максимуму среди первого элемента;
• idx = 1, что верно.

Теперь рассмотрим очередной элемент a[i].

• Если a[i] > mx, значит найден новый, более большой максимум. Тогда правильно обновить и значение максимума, и его индекс.
• Если a[i] <= mx, то текущий максимум не меняется.
  • Если a[i] < mx, это очевидно.
  • Если a[i] == mx, обновлять индекс нельзя, потому что нужен индекс первого появления, а первое уже было раньше.

Значит, после каждого шага сохраняется такой инвариант: mx — максимум среди уже просмотренных элементов, а idx — индекс его первого вхождения.

После завершения прохода это верно уже для всего массива, значит алгоритм корректен.

Сложность

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

Код на C++17

#include <iostream>
using namespace std;

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

    long long x;
    cin >> x;
    long long mx = x;
    int idx = 1;

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

    cout << mx << " " << idx << "\n";
    return 0;
}

Код на Python 3

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

mx = a[0]
idx = 1

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

print(mx, idx)