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
#include "bits/stdc++.h"
using namespace std;
#define rep(i,a,b) for(int i=(a); i<(b); ++i)
#define all(x) x.begin(),x.end()
#define sz(x) int(x.size())
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<vi> vvi;

int main(){
    cin.tie(NULL),ios::sync_with_stdio(false);
    
    int n,k; cin >> n >> k;

    vi a(n);
    for(auto& c : a) cin >> c;
    ll ans = accumulate(all(a),0ll);

    vi vis(n);
    priority_queue<pair<int,int>> pq;
    rep(i,0,n) pq.push({a[i],i});

    while(sz(pq)) {
        auto [h, at] = pq.top(); pq.pop();
        if (vis[at]) continue;
        vis[at] = 1;

        if (at > 0 and !vis[at-1] and a[at] - k > a[at-1]){
            a[at-1] = a[at] - k;
            pq.push({a[at-1], at-1});
        }
        if (at+1 < n and !vis[at+1] and a[at] - k > a[at+1]){
            a[at+1] = a[at] - k;
            pq.push({a[at+1], at+1});
        }
    }

    cout << accumulate(all(a),0ll) - ans << '\n';
}