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
49
50
51
52
53
54
55
56
57
// Template generated by Clank
#include<bits/stdc++.h>
using namespace std;
#define st first
#define nd second
#define all(x) x.begin(), x.end()
#define BOOST cin.tie(NULL); ios_base::sync_with_stdio(false);
// #define int ll
typedef long long ll;


int32_t main(){
    BOOST;
    int n, k; cin >> n >> k;
    vector<int> a(n + 2, 0);
    vector<int> ca(n + 2, 0);
    // vector<pair<int,int>> order(n);
    set<pair<int,int>> order;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
        ca[i] = a[i];
        order.insert({a[i], i});
        // order[i - 1] = {a[i], i};
    }
    // sort(all(order), greater<pair<int,int>>());

    while(!order.empty()){
        auto it = order.rbegin();
        int cidx = (*it).nd;
        order.erase((*it));
        if(cidx - 1 > 0 && a[cidx - 1] + k < a[cidx]){
            order.erase({a[cidx - 1], cidx - 1});
            a[cidx - 1] += a[cidx] - a[cidx - 1] - k;
            order.insert({a[cidx - 1], cidx - 1});
        }
        if(cidx + 1 <= n && a[cidx + 1] + k < a[cidx]){
            order.erase({a[cidx + 1], cidx + 1});
            a[cidx + 1] += a[cidx] - a[cidx + 1] - k;
            order.insert({a[cidx + 1], cidx + 1});
        }
    }

    ll ans = 0;
    for(int i = 1; i <= n; i++){
        ans += a[i] - ca[i];
    }
    cout << ans << "\n";
    // for(int i = 0; i < n; i++){
    //     int cidx = order[i].nd;
    //     ll tmp = max(max(a[cidx - 1], a[cidx + 1]) - a[cidx], k) - k;
    //     a[cidx] += tmp;
    //     ans += tmp;
    //     // cout << cidx << " " << tmp << "\n";
    // }
    // cout << ans << "\n";
    return 0;
}