1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <bits/stdc++.h>
using namespace std;

#define all(a) (a).begin(), (a).end()

typedef long long ll;
typedef vector<int> vi;
typedef vector<long long> vll;
typedef pair<int,int> pii;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n,k;
    cin>>n>>k;
    vector<int> as(n);
    for (int& i : as) cin>>i;

    priority_queue<pii> q;
    for (int i=0; i<n; i++) q.push({as[i],i});
    vector<bool> visited(n,false);

    ll res = 0;
    while (!q.empty()) {
        auto [val,ind] = q.top();
        q.pop();
        if (visited[ind]) continue;
        if (val != as[ind]) continue;
        visited[ind] = true;

        if (ind != n-1) if (as[ind]-as[ind+1]>k) {
            res += as[ind]-as[ind+1]-k;
            as[ind+1] = as[ind]-k;
            q.push({as[ind+1],ind+1});
        }
        if (ind != 0) if (as[ind]-as[ind-1]>k) {
            res += as[ind]-as[ind-1]-k;
            as[ind-1] = as[ind]-k;
            q.push({as[ind-1],ind-1});
        }
    }

    cout<<res<<'\n';

    return 0;
}