Кевин и Нивек соревнуются за титул «Лучший Кевин». Их цель — определить победителя за \(n\) матчей.
\(i\)-й матч может быть одного из двух типов:
- Тип 1: Кевину нужно потратить \(a_i\) времени, чтобы победить Нивека и выиграть матч. Если Кевин не потратит на этот матч \(a_i\) времени, Нивек выиграет матч.
- Тип 2: Исход этого матча зависит от их исторических данных. Если количество побед Кевина больше или равно количеству побед Нивека до этого матча, то Кевин выиграет. В противном случае выиграет Нивек.
Кевин хочет узнать, какое минимальное количество времени ему нужно потратить, чтобы выиграть как минимум \(k\) матчей.
Выведите ответы для \(k = 0, 1, \ldots, n\).
Выходные данные
Для каждого набора входных данных выведите \(n + 1\) целое число. \(i\)-е целое число представляет минимальное количество времени для победы по крайней мере в \(i-1\) матче.
Примечание
В первом наборе входных данных все матчи относятся к типу 2. Кевин автоматически выигрывает все матчи.
Во втором наборе входных данных все матчи относятся к типу 1. Кевин может выбирать матчи в порядке возрастания \(a_i\).
В третьем наборе входных данных:
- Если Кевин потратит \(a_1\) времени на матч \(1\), он может выиграть матчи \(1, 2, 3, 4\).
- Если Кевин потратит \(a_5\) времени на матч \(5\), он может выиграть матч \(5\).
- Если Кевин потратит \(a_1\) времени на матч \(1\) и \(a_5\) времени на матч \(5\), он может выиграть все матчи.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
5
-1 -1 -1 -1 -1
5
3 2 5 4 1
5
100 -1 -1 -1 1
|
0 0 0 0 0 0
0 1 3 6 10 15
0 1 100 100 100 101
|