410530: GYM104035 5 Задача о числах

У Васи на бесконечной бумажке друг за другом записано $$$n$$$ положительных чисел: $$$a_1, a_2, \ldots, a_n$$$.

Васе стало скучно, и он решил себя развлечь следующим занятием: он стирает первое ещё не стёртое число на бумажке $$$k$$$, а затем записывает $$$k$$$ раз число $$$k$$$ после всех записанных чисел. Так он продолжает делать до бесконечности.

Например, если на бумажке изначально были записаны числа $$$3, 1, 4$$$, то сначала он сотрёт тройку и три раза её запишет в конец, тем самым получит на бумажке $$$1, 4, 3, 3, 3$$$. Затем, он сотрёт единицу и один раз запишет её в конец, получив $$$4, 3, 3, 3, 1$$$. И так далее.

Какое число он сотрёт $$$m$$$-м?

В первой строке вводится целое число $$$n$$$ ($$$1 \le n \le 10^5$$$).

Во второй строке вводится целое число $$$m$$$ ($$$1 \le m \le 10^9$$$).

В следующих $$$n$$$ строках вводятся целые числа $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$).

Выведите единственное целое число — число, которое Вася сотрёт $$$m$$$-м по счёту.

В этой задаче 25 тестов, каждый из них независимо оценивается в 4 балла.

Решения, правильно работающие при $$$m \le 2n$$$ и $$$a_1 + a_2 + \ldots + a_n \le 5 \cdot 10^5$$$, будут оцениваться в 20 баллов.

Решения, правильно работающие при $$$m \le 2n$$$, будут оцениваться в 40 баллов.

3
2
3
1
4

1

3
8
3
1
4

4