Iceberg Hopping

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

Author:
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

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
0

Sample Output 2

0