405434: GYM101962 F Renanzinho and His Toys

Renanzinho is a slow weirdo. In his 8th aniversary, there were candies, clowns, bouncers and even a delicious strogonoff. For him, the best part of the party, though, was unwrapping the gifts.

Renan, his father, gave to him $$$N$$$ toys. The height of the $$$i$$$-th toy is given by $$$A_i$$$. Renanzinho loved the toys and is planning to spend the night rearranging them. He wants to arrange his toys into groups such that every group has a size between $$$L$$$ and $$$R$$$ and contains only contiguous toys (every group of toys is a contiguous subsequence of $$$1, 2, \dots, N$$$). Also, every toy should be in exactly one group.

Suppose that Renanzinho splits his toys in $$$K$$$ groups. The happiness of Renanzinho is arbitrarily defined as the minimum value among the maximum toy height of each group.

Since Renanzinho is a slow kid you need to calculate the maximum happiness he can achieve if he splits the toys optimally.

The first line of the input contains three integers $$$N, L, R$$$ ($$$1 \leq N \leq 10^{5}$$$;$$$ 1 \leq L \leq R \leq N$$$).

The second line of the input contains $$$N$$$ integers. The $$$i$$$-th of them is $$$A_i$$$ ($$$1 \leq A_i \leq 10^{9}$$$), the height of his $$$i$$$-th toy.

It's guaranteed that there is at least one way Renanzinho can split the toys.

Output one line, the maximum value of happiness Renanzinho can achieve.

9 3 5
12 7 6 2 3 1 19 22 6

12

7 2 6
30 3 29 2 28 1 27

29