Задача №115150. Выборы
В Берляндии проходят выборы!
В выборах участвуют \(n\) кандидатов, пронумерованных от \(1\) до \(n\). У \(i\)-го из них есть \(a_i\) фанатов. Так же дополнительно есть \(c\) избирателей, которые не определились с любимым кандидатом, назовем их неопределившимися . Неопределившиеся избиратели, придя на избирательный пункт, проголосуют за человека с наименьшим номером.
В выборах побеждает кандидат, который набрал максимальное количество голосов, а если максимальное количество голосов набрали несколько кандидатов, то среди таких побеждает человек с минимальным номером.
Такие выборы вам показались слишком скучными и предсказуемыми, поэтому вы решили не допустить некоторых кандидатов к ним. Если вы не допустите кандидата с номером \(i\) к выборам, то все \(a_i\) его фанатов станут неопределившимися избирателями, и на выборах проголосуют за допущенного кандидата с минимальным номером.
Вам стало интересно узнать для каждого \(i\) от \(1\) до \(n\), какое минимальное число кандидатов надо не допустить к выборам, чтобы кандидат с номером \(i\) выиграл выборы.
В первой строке вводятся два целых числа \(n\), \(c\) (\(1 \le n \le 200000\), \(0 \le c \le 10^9\)) — количество кандидатов на выборах и количество неопределившихся избирателей.
Во второй строке вводятся \(n\) целых чисел \(a_1\), \(a_2\), \(\ldots\), \(a_n\) (\( 0 \le a_i \le 10^9 \)) — количество фанатов каждого кандидата.
Выведите \(n\) чисел, \(i\)-е из них должно быть равно минимальному количеству кандидатов, которых нужно не допустить к выборам, чтобы кандидат с номером \(i\) победил.
В первом примере для человека номер \(1\) ответ \(0\), ведь если мы допустим всех кандидатов к выборам, то он победит, так как за него проголосует \(1\) неопределившийся избиратель.
Во втором примере для победы первого кандидата будет достаточно не допустить к выборам второго кандидата, тогда он останется единственным кандидатом и победит на выборах.
В данной задаче \(25\) тестов, помимо тестов из условия, каждый из них оценивается в \(4\) балла.
Решения, корректно работающие для \(n \le 10\), наберут не менее \(20\) баллов.
Решения, корректно работающие для \(n \le 1000\), наберут не менее \(40\) баллов. Дополнительно, решения, корректно работающие для случая, когда у всех кандидатов одинаковое число фанатов, наберут не менее \(20\) баллов.
3 1 2 0 3
0 1 2
2 3 0 10
1 0