Steve has \(N\) minecarts labelled
from \(1\) to \(N\) lined up on a track in a row from left
to right. Initially, there are \(a_i\)
gems in the \(i\)-th minecart.

Steve wants the minecarts to be arranged in a row such that the
number of gems in each minecart is non-decreasing from left to right. To
do this, he plans to build a side track to the right of all of the
minecarts that splits off from the main track. Steve can move minecarts
that are on the left of the side track into the side track, allowing
other minecarts on its left to move past it on the main track. Minecarts
moved into the side track can be moved back into the main track one at a
time: a minecart on the side track will move back to the left of the
side track and to the right of all other minecarts which are on the left
of the side track. The last minecart moved into the side track must be
the first minecart to be moved back out: that is, the side track follows
a last-in, first-out method. The side track can be used any number of
times. Finally, once a minecart is moved to the right of the side track,
it can no longer be moved to the left. Below is an example sequence of
moves that can be made with \(5\)
minecarts beginning from the initial position:

Steve has \(K\) spare gems, and he
can distribute any number of them into the minecarts that are
empty. Steve has yet to build the side track, and he
wants to limit the side track capacity to save work. A side track with a
specific capacity can only store up to that many minecarts. For example,
if the side track had a capacity of \(1\), we would not be able to make the moves
in the diagrams above, which would require a capacity of at least \(2\). Given that Steve places his spare gems
into the minecarts optimally, what is the minimum capacity of the side
track that needs to be built?

\((1 \leq N \leq 3\times10^5,~ 0 \leq K \leq 10^{12})\)
\((0\leq a_i\leq 10^6)\)

The first line of input will consist of two space-separated integers
\(N\) and \(K\) \((1 \leq N \leq 3\times10^5,~ 0 \leq K \leq 10^{12})\).

The next line contains \(N\)
integers \(a_1,\dots,a_n\) \((0\leq a_i\leq 10^6)\), where the \(i\)-th
integer indicates the number of gems in the \(i\)-th minecart.

Output a single integer, the minimum capacity of the side track that
needs to be built given that Steve distributes up to \(K\) gems among the empty minecarts
optimally.

생성자가 기록되지 않았습니다.

출처 CCC 2026 Senior