A river contains a starting rock at position 0 and an ending rock at position L. Between them there are N intermediate rocks, each at a distinct coordinate Di (0 < Di < L). A cow must jump from rock to rock, never skipping ahead by less than some distance. To challenge the cows, we can remove exactly M of the intermediate rocks (the start and end rocks are fixed). The problem is to determine the maximum possible value of the shortest jump distance after removing M rocks.

We can model this as an optimization over the minimum allowable gap. Let min_gap be the smallest distance we want to enforce between consecutive rocks. A greedy strategy tells us how many rocks must be removed to achieve that gap: scan the rocks from start to end, keep a rock if its distance from the last kept rock is at least min_gap; otherwise remove it. If the total removals are ≤ M, the min_gap is feasible.

Because the answer lies between 1 and L and the feasibility is monotonic (if a larger gap is possible, any smaller gap is also possible), we can binary search for the largest feasible min_gap.

Input format

• Line 1: three integers L, N, M (1 ≤ L ≤ 1,000,000,000; 0 ≤ N ≤ 50,000; 0 ≤ M ≤ N)
• Next N lines: each contains the position of an intermediate rock (0 < position < L), all distinct.

Output format

• A single integer: the maximum achievable minimum jump distance.

Example

Input:
25 5 2
2
14
11
21
17

Output:
4

After sorting the rocks: [2, 11, 14, 17, 21], adding the endpoint 25. With M=2 removals, one optimal choice leaves rocks [0, 2, 11, 17, 25] giving gaps 2, 9, 6, 8 → minimum 2? Wait, actually the sample answer is 4. Let's re-evaluate: if we remove rocks at 14 and 21, remaining positions are 0, 2, 11, 17, 25, gap are 2, 9, 6, 8 → min=2. But answer is 4, so another removal is beetter: remove 2 and 14, remaining 0, 11, 17, 21, 25, gaps 11, 6, 4, 4 → min=4. So the minimum gap can be at most 4.

Soluttion outline Define a function canAchieve(minDist) that returns true if we can leave a set of rocks where every consecutive distance is at least minDist by removing at most M rocks. Walk through the sorted positions (including the end rock L). Keep track of the last rock we decided to keep (prev). For each rock, if rock - prev < minDist we must remove it (increment removal counter); otherwise we keep it by setting prev = rock. At the end, check whether removals <= M.

Binary search for the maximum minDist in the range [1, L] using the typical pattern.

Implementation

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;

bool canAchieve(ll minDist, const vector<ll>& rocks, int maxRemovals) {
    int removed = 0;
    ll prev = 0;
    for (ll r : rocks) {
        if (r - prev < minDist) {
            removed++;
        } else {
            prev = r;
        }
    }
    return removed <= maxRemovals;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    ll L, N, M;
    cin >> L >> N >> M;
    vector<ll> pos(N);
    for (int i = 0; i < N; ++i) cin >> pos[i];
    sort(pos.begin(), pos.end());
    pos.push_back(L);
    ll low = 1, high = L, ans = 0;
    while (low <= high) {
        ll mid = (low + high) / 2;
        if (canAchieve(mid, pos, M)) {
            ans = mid;
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    cout << ans << "\n";
    return 0;
}