Problem Description

A little frog lives by a river and wants to go to the school on the other side to study. The frog plans to jump on stones in the river to reach the opposite bank.

The stones in the river are arranged in a straight line. Each jump must land on a stone or on a bank. Each stone has a height. Every time the frog jumps from a stone, the height of that stone decreases by $1$. When a stone’s height decreases to $0$, the frog can no longer land on that stone (it is allowed that after some jump, the stone’s height becomes $0$).

The frog needs to attend school for $x$ days, so it must make $x$ round trips, i.e. cross the river $2x$ times. If the frog has a jumping ability $y$, it can jump a distance of at most $y$.

Find the minimum jumping ability required so that the frog can use these stones to finish attending school for $x$ days.

Input Format

The first line contains two integers $n, x$, representing the width of the river and the number of days the frog needs to go to school. Note that $2x$ is the actual number of crossings.

The second line contains $n-1$ non-negative integers $H_{1}, H_{2}, \cdots, H_{n-1}$. Here, $H_{i} > 0$ means there is a stone of height $H_{i}$ at distance $i$ from the frog’s home bank, and $H_{i} = 0$ means there is no stone at that position.

Output Format

Output one line containing one integer, representing the minimum jumping ability the frog needs.

5 1
1 0 1 0

4

Hint

Sample Explanation

Since there are only two stones with height $1$, each direction of the round trip can only use one stone. The distance between the first stone and the opposite bank is $4$. If the frog’s jumping ability is $3$, it cannot meet the requirement. Therefore, the frog needs a minimum jumping ability of $4$.

Constraints and Conventions

For $30\%$ of the testdata, $n \leq 100$.

For $60\%$ of the testdata, $n \leq 1000$.

For all testdata, $1 \leq n \leq 10^{5}$, $1 \leq x \leq 10^{9}$, $0 \leq H_{i} \leq 10^{4}$.

Lanqiao Cup 2022 Provincial Contest A Group, Problem F.

Translated by ChatGPT 5