1. Идея

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

Самый прямой способ:

• считать все результаты в массив;
• отсортировать массив;
• взять элемент с индексом k - 1, потому что в массиве индексация начинается с 0, а места в условии — с 1.

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

1. После сортировки по неубыванию:

   • на первом месте будет минимальный элемент;
   • на втором — следующий;
   • ...
   • на k-м месте будет элемент a[k - 1].

2. В задаче не требуется восстанавливать исходного участника, нужен только сам результат.

3. Повторы не мешают решению. Если одно и то же значение встречается несколько раз, после сортировки оно просто займет несколько соседних позиций.

4. Ограничение n <= 2 * 10^5 позволяет спокойно отсортировать массив стандартной сортировкой.

3. Алгоритм

1. Считать n и k.
2. Считать массив из n чисел.
3. Отсортировать массив по возрастанию.
4. Вывести элемент a[k - 1].

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

После сортировки массив упорядочен по неубыванию. Это означает, что элементы стоят ровно в том порядке, который требуется в условии.

Так как нумерация мест начинается с 1:

• элемент на 1-м месте имеет индекс 0,
• элемент на 2-м месте имеет индекс 1,
• элемент на k-м месте имеет индекс k - 1.

Значит, после сортировки ответом будет именно a[k - 1].

5. Сложность

Сортировка массива из n элементов работает за O(n log n).

Остальные действия — чтение входа и вывод ответа — занимают O(n).

Итоговая сложность:

• по времени: O(n log n)
• по памяти: O(n)

6. Код на C++17

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

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

    vector<long long> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    sort(a.begin(), a.end());

    cout << a[k - 1] << '\n';
    return 0;
}

7. Код на Python 3

n, k = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
print(a[k - 1])