Swimming Competition

Time limit1sMemory limit1024 MB

Summary

Split a sorted list of N swimmer times into consecutive heats of size A to B, minimizing the largest within-heat gap between fastest and slowest.

Level: Medium6 of 10
Topics: Binary search, Greedy, Dynamic programming, Array
Solved: No attempts yet

Problem

Any student who wishes may take part in the open student swimming competition. Because there is no advance registration, the organizers never know beforehand how many contestants will show up.

The pool has 8 lanes, but this time fewer students arrived than expected, so the organizers decided to split them into smaller heats of no fewer than $A$ and no more than $B$ swimmers each.

The organizers also want every race to be as exciting as possible, with swimmers of similar ability competing together.

Write a program that assigns the arriving students to heats so that the largest value — taken over all heats — of the absolute difference between the slowest swimmer's and the fastest swimmer's average finishing time within a heat is as small as possible.

Input

The first line contains three space-separated integers: the number of participants who arrived $N$ , and the minimum $A$ and maximum $B$ number of swimmers allowed in one heat.

Each of the next $N$ lines contains a time $t_i$ , the average time in which a swimmer covers the distance, given in non-decreasing order ( $t_i \le t_{i+1}$ ).

The input is always such that a valid split into heats exists.

Output

Over all valid ways to split every participant into heats, consider the largest difference, within a single heat, between the slowest and the fastest swimmer's time. Print the smallest value this maximum can take, as a single integer.

Constraints

$2 \le N \le 500\,000$
$2 \le A \le B \le 8$
$1 \le t_i \le 1\,000\,000$

Examples2

Example 1
Input
```
5 2 4
1
1
3
3
4
```
Expected output
```
1
```
Example 2
Input
```
8 3 5
1
1
1
5
8
8
8
10
```
Expected output
```
4
```