Iceberg Hopping

Submit solution

Points: 10 (partial)
Time limit: 1.0s
Memory limit: 128M

Problem type

Some penguins are going iceberg-hopping!

There are initially \(N\) floating icebergs, each staying afloat for another \(t_i\) seconds. After \(t_i\) seconds the \(i\)-th iceberg will sink and become unusable.

Bob the penguin can jump across a maximum of \(K\) icebergs at once (see the sample explanation for more information) and always starts on the first iceberg.

What is the latest time Bob can start his iceberg-hopping in order to reach the \(N\)-th iceberg? Bob is a very fast penguin, we will assume that no time will be wasted when he's iceberg-hopping.

Input Specification

The first line of the input will contain two integers \(N\) and \(K\) \((1 \le N, K \le 10^5)\), indicating the number of icebergs and the number of icebergs he can jump over.

The next line of the input will each contain an integer \(t_i\) ranging from \(0\) to \(10^9\) inclusive, indicating the number of seconds remaining before the \(i\)-th iceberg becomes unusable.

Output Specification

Output an integer, representing the latest time (in seconds) Bob can start his iceberg-hopping run.

Sample Input 1

5 2
2 1 0 1 3

Sample Output 1


Sample Explanation 1

When \(t = 0\), all icebergs are still floating. Bob can reach the iceberg \(5\) in multiple ways.

When \(t = 1\), there is only one way to reach the last iceberg. Bob must jump from iceberg \(1\) to iceberg \(2\), iceberg \(2\) to iceberg \(4\), and finally from iceberg \(4\) to iceberg \(5\).

When \(t = 2\), iceberg \(2\) and \(4\) both sink, leving no possible way for Bob to reach the end. This indicates that \(t = 1\) is the last possible time Bob can start.

Sample Input 2

1 1

Sample Output 2



There are no comments at the moment.