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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
#include <bits/stdc++.h>
#include <iomanip>
 
using namespace std;
using ll = long long ;
using pii = pair <int,int> ;
using pll = pair<ll,ll> ;
using vi = vector <int> ; 
using vll = vector < ll > ;
using tiii = tuple<int,int,int> ; 
using ld = long double ; 

#define cYes {cout<<"YES\n";return;}
#define cNo {cout<<"NO\n";return;}
#define bra(x) "[" << (x) << "] "
#define ndl '\n' ;
#define all(x) (x).begin() , (x).end() 
#define sz(x) (int)(x).size() 
#define nd second 
#define st first
#define vvi vector<vector<int>> 

#define DEBUG
#ifdef DEBUG 
#define dbg(x) cerr << #x << " = " << x << endl 
#else
#define DEBUG 
#endif

int N , K ;


int main(){
    ios_base::sync_with_stdio(false) ; cin.tie(0) ;
    cin >> N >> K ;
    vector < int >  arr(N+8) ;
    set < pii > stek ;
    for(int i=1;i<=N;i++){
        int a ; cin >> a ;
        arr[i] = a ;
        stek.insert( {a,i} ) ;
    }
    int answer = 0 ;
    
    // for(auto [a,b] : stek ){
    //     cout << a << ' ' << b << endl ;
    // }
    
    
    // sort( all( arr ) ) ; reverse( all(arr) ) ;
    vi tab(N+71,-1) ;
    while( !stek.empty() ){
        auto it = prev( stek.end() ) ;
        auto [val,idx] = *it ;
        stek.erase(it) ;
        //cout << " val , idx " << val << ' ' << idx << endl ;
        if( tab[idx] != -1 ) continue ;
        
        // {
        //     cout << endl ;
        //     for(int i=1;i<=N;i++){
        //         dbg(i) ;
        //         cout << tab[i] << ' ' ;
        //     }
        //     cout << endl ;
        // }
        
        int lewy = tab[idx-1] ;
        int prawy = tab[idx+1] ;
        tab[idx] = val ;
        if( idx > 1 and lewy < val ){
            stek.insert( { max(0,val-K) , idx-1 } ) ;
        }
        if( prawy < val and idx < N ){
           // cout << "jestem " << val << ' ' << idx << endl ;
            stek.insert( { max(0,val-K) , idx+1 } ) ;
        }
        
    }
    
    
    // for(int i=1;i<=N;i++){
    //     dbg(i) ;
    //     dbg(tab[i]) ;
    // }
    
    for(int i=1;i<=N;i++){
        int res = tab[i] - arr[i] ;
        assert( res >= 0 ) ;
        answer += res ;
    }
    cout << answer ;
    
    return 0 ;
}