Bike stations

binary search greedy maps and navigation contests

There are n crossroads along a street, and the distance from the start of the street to each is known. Bike rental stations must be put at k of them so that the two closest stations are as far apart as possible. What is the largest such distance? Each k in a list needs its own answer.

The second and third tests are the 177 crossroads of the longest shortest route across the centre of Almaty: 24.1 km along the streets from OpenStreetMap.

Input

The first line holds n and q (2 ≤ n ≤ 10⁵, 1 ≤ q ≤ 10). The second holds n distinct distances in metres, from 0 to 10⁹. The third holds q numbers k (2 ≤ k ≤ n).

Output

For each k, the largest possible distance between the two closest stations.

Examples

Example 1

Input

5 3
1 2 4 8 9
2 3 5

Output

8
3
1

Limits

Time · Python: 5000 ms
Time · Go: 1000 ms
Memory: 256 MB
Judging: 6 tests

Walkthrough

Open it step by step: each step gives away a little more. You can jump straight to the solution, but a problem solved with one hint stays with you longer.

1Hint 1

The question “can k stations be placed so that any two are at least d apart” is easier to answer than the original one. And if it can be done for d, it can be done for any smaller d as well.

2The idea

Look for the largest d with the answer “yes” by binary search. The check is greedy: put the first station at the first crossroads, and each next one at the first crossroads at least d from the previous station. If k stations are placed this way, the answer is yes.

3Walkthrough

Why the greedy check is never wrong: placing a station earlier is never worse, since all the following stations get more room. Any valid placement can be shifted left towards the greedy one without breaking the condition.

Here we look for the last yes rather than the first, so the middle is rounded up: (lo + hi + 1) / 2. With rounding down, at hi = lo + 1 the search loops forever.

3+Solution

4Complexity

A range of up to 10⁹ takes 30 checks of O(n): O(n log D) per k, plus sorting.

5Common mistakes

Placing stations every so many crossroads. The crossroads are spaced unevenly: on the route through Almaty neighbouring crossroads can be two metres apart or three kilometres; a typical gap is about 80 metres.
The middle rounded down. When looking for the last value that fits, this is an endless loop on two neighbouring numbers.
Unsorted input. The greedy check goes from left to right and needs sorted distances.

Algorithms behind it

SRT Technique Binary search on the answer If checking an answer is easier than finding it, and the check is monotone, search for the answer by halving. O(log D · cost of a check) 2 problems PAR Technique Greedy algorithms The best step now with no looking back: when it is optimal, when almost, and how to prove it. usually O(n log n): a sort or a heap 2 problems