21036.cpp

#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)

#define ll long long
using namespace std;

const ll INF = 1e9 + 7;
const ll DIV = 987654321;

ll n, m, k;
ll arr[101010];

ll val[101010];

int main()
{
    fastio;
    cin >> n >> m >> k;
    vector<ll> tmp;
    for(int  i=0 ;i < m;i++){
        cin >> arr[i];
        tmp.push_back(arr[i]);
    }

    sort(tmp.begin(), tmp.end());

    tmp.erase(unique(tmp.begin(), tmp.end()), tmp.end());
    for(int i =0 ;i < tmp.size();i++){
        arr[i] = tmp[i];
    }
    m = tmp.size();

    priority_queue<pair<ll,ll>> pq;

    for(int i =0 ;i < m;i++){
        ll l, r;
        if(i == 0){
            l = 1;
        }
        else{
            l = (arr[i] + arr[i - 1] + 1) / 2;
        }

        if(i == m - 1) r = n;
        else{
            r = (arr[i] + arr[i+1])/2;
        }

        val[i] = r - l + 1;

        pq.push({val[i], i});
    }

    ll ans = 0;

    for(int i = 0; i < min(m,k);i++){
        while(pq.top().first != val[pq.top().second]){
            auto[a, idx] = pq.top();
            pq.pop();
            pq.push({val[idx], idx});
        }

        auto[x, idx] = pq.top();
        pq.pop();

        ans += x;

        if(idx > 0){
            if(( arr[idx] - arr[idx - 1]) % 2 == 0){
                val[idx - 1]--;
            }
        }

        if(idx + 1 < m){
            if((arr[idx + 1] - arr[idx]) % 2 == 0){
                val[idx + 1]--;
            }
        }
        
    }

    cout << ans << "\n";

    return 0;
}