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;

int k;
vector <int> a;
int ans = 0;

void solve(int l, int r) {
    int maxi = -1, i = -1;
    for(int j = l; j <= r; ++j) if(a[j] > maxi) {
        maxi = a[j];
        i = j;
    }

    if(i - 1 >= l) {
        if(a[i] - a[i - 1] > k) {
            ans += a[i] - a[i - 1] - k;
            a[i - 1] = a[i] - k;
        }
        solve(l, i - 1);
    }
    if(i + 1 <= r) {
        if(a[i] - a[i + 1] > k) {
            ans += a[i] - a[i + 1] - k;
            a[i + 1] = a[i] - k;
        }
        solve(i + 1, r);
    }
}

int main() {
    int n; scanf("%d%d", &n, &k);
    a.resize(n);
    for(int &x : a) scanf("%d", &x);

    solve(0, n - 1);
    printf("%d\n", ans);

    return 0;
}