1. Идея

Нужно найти:

• минимальную стоимость среди всех рейсов;
• номер рейса, где эта минимальная стоимость встретилась впервые.

Для этого достаточно один раз пройти по массиву стоимостей и поддерживать:

• текущий минимум mn;
• позицию этого минимума pos.

Если встретили число строго меньше текущего минимума, обновляем и минимум, и его позицию.

Важно именно сравнение x < mn, а не x <= mn. Тогда при одинаковых минимальных значениях сохранится первая позиция.

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

1. Нумерация рейсов начинается с 1, а не с 0.
2. Первый элемент можно сразу считать текущим минимумом.
3. Если очередная стоимость равна текущему минимуму, позицию менять не нужно, потому что требуется первое вхождение.
4. Достаточно одного прохода по данным, хранить что-то сложное не нужно.

Пример:

5 -3 7 -3 2

• сначала mn = 5, pos = 1
• видим -3, это меньше 5, значит mn = -3, pos = 2
• 7 не меньше -3
• -3 равно -3, позицию не меняем
• 2 не меньше -3

Ответ: -3 2.

3. Алгоритм

1. Считать n.
2. Считать стоимости.
3. Взять первую стоимость как текущий минимум:
   • mn = первый элемент
   • pos = 1
4. Пройти по остальным элементам:
   • если текущая стоимость меньше mn, то:
     • обновить mn
     • запомнить её номер
5. Вывести mn и pos.

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

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

• mn — минимальная стоимость среди уже просмотренных рейсов;
• pos — номер первого рейса, на котором этот минимум встречается.

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

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

После завершения прохода просмотрены все рейсы, значит mn — минимум во всём массиве, а pos — номер первого рейса с такой стоимостью.

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 mn = x;
    int pos = 1;

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

    cout << mn << " " << pos << "\n";
    return 0;
}

7. Код на Python 3

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

mn = a[0]
pos = 1

for i in range(1, n):
    if a[i] < mn:
        mn = a[i]
        pos = i + 1

print(mn, pos)