Bradley the Unicorn wants to get to sugar candy mountain. (to meet Charlie the Unicorn). However, the route to sugar candy mountain is unforunately littered with lots of lots of, you guess what? CANDY!
The route to sugar candy mountain brings Bradley to a river with N pebbles arranged in a straight line. To cross the river, Bradley can jump from pebbles to pebbles. He can jump up to K pebbles ahead at one time.
"Too much sugar will make me go to the imaginary axis! Or become a Snake!" -- says Bradley. Therefore, Bradley wants to travel on a route where by the maximum number of candies per pebble is reduced.
It is assumed that he can jump from the his starting shore to the first K pebbles and he can jump from any of the last K pebbles to the other shore.
The first line of input consists of 2 integers, N followed by K.
The second line of input will consist of N integers. The ith integer represents the number of sweets on the ith pebble.
Output a single integer. The integer should represent the maximum number of candies per pebble that Bradley will encounter if he takes the route where the maximum number of candies per pebble is reduced.
(i.e. Find the route where the maximum number of candies encountered in a pebble on the route is reduced, and output that number)
The number of candies on each pebble will be a non-negative integer that fits into a 32-bit signed integer.
Subtask 1 (25%): 0 < N ≤ 100
Subtask 2 (25%): 0 < N ≤ 1000
Subtask 3 (50%): 0 < N ≤ 100000
10 4 1 2 3 4 5 6 7 8 9 10
7
The route is start -> 1 -> 5 -> 7 -> end
10 3 0 1 3 2 4 8 2 7 3 5
3
The route is start -> 0 -> 2 -> 2 -> 3 -> end
| Subtask | Score |
|---|---|
| 1 | 25 |
| 2 | 25 |
| 3 | 50 |
| 4 | 0 |