Minimizing Maximum Difficulty in Consecutive Puzzle Segments

Bob is organizing a treasure hunt in which each participant is required to solve a series of puzzles arranged in a linear sequence. Every participant will solve exactly \(M\) consecutive puzzles and the difficulty of a segment is defined as the maximum difficulty of the puzzles within that segment. Bob wants to partition the sequence into contiguous segments of \(M\) puzzles (with the last segment possibly having less than \(M\) puzzles) in such a way that the maximum difficulty any participant faces (i.e. the maximum of the segment difficulties) is minimized.

Your task is to compute this minimum possible value of the maximum difficulty by dividing the puzzles sequentially in groups of \(M\). Specifically, if the puzzles are given in an array of length \(N\), divide the array into contiguous segments: \(\text{segment}_1 = a_1, a_2, \ldots, a_M\), \(\text{segment}_2 = a_{M+1}, \ldots\), and so on. For each segment compute its maximum difficulty, and then take the maximum over these segment values, which is the answer.

Examples:

• For \(N=7\), \(M=3\) and difficulties [1, 3, 4, 7, 6, 2, 5], the segments are [1, 3, 4], [7, 6, 2], and [5]. Their maximum difficulties are 4, 7, and 5, so the answer is \(7\).
• For \(N=5\), \(M=2\) and difficulties [9, 4, 6, 8, 3], the segments are [9, 4], [6, 8], and [3]. Their maximum difficulties are 9, 8, and 3, so the answer is \(9\).

inputFormat

The first line contains two space-separated integers \(N\) and \(M\), representing the number of puzzles and the number of consecutive puzzles each participant will solve, respectively.

The second line contains \(N\) space-separated integers representing the difficulty levels of the puzzles.

outputFormat

Output a single integer which is the minimum possible value of the maximum difficulty faced by any participant when the puzzles are divided into segments of consecutive \(M\) puzzles.

## sample

7 3
1 3 4 7 6 2 5

7

</p>