// Source: https://usaco.guide/general/io #include <bits/stdc++.h> using namespace std; using ll = long long; #define eb emplace_back // faster than push_back xD // pbds UwU #include <ext/pb_ds/assoc_container.hpp> using namespace __gnu_pbds; #define oset tree<ll, null_type,less<ll>, rb_tree_tag,tree_order_statistics_node_update> // use pair for ms // my io library :D #define m1(x) template<class T, class... U> void x(T&& a, U&&... b) #define m2(x) (ll[]){(x forward<U>(b),0)...} m1(pr){cout << forward<T>(a); m2(cout << " " <<); cout << "\n";} m1(re){cin >> forward<T>(a); m2(cin >>);} ll n, h, base = 1; vector<ll> treeseg; ll rangemin(ll a, ll b){ a += base; b += base; ll s = 1e18; while (a <= b){ if (a%2 == 1) s = min(s, treeseg[a++]); if (b%2 == 0) s = min(s, treeseg[b--]); a /= 2; b /= 2; } return s; } int main() { ios::sync_with_stdio(0); cin.tie(0); re(n, h); vector<ll> s(n); for (ll i{}; i < n; i++) re(s[i]); ll maxl = max({*max_element(s.begin(), s.end()), s[0] + (n-1)*h, s[n-1] + (n-1)*h}); while (base <= maxl) base *= 2; treeseg.resize(2*base); vector<vector<ll>> dp(n, vector<ll>(maxl+1, 1e18)); for (ll i{}; i <= maxl; i++){ dp[0][i] = abs(s[0]-i); } for (ll i = 1; i < n; i++){ fill(treeseg.begin(), treeseg.end(), (ll)1e18); ll low = max({0LL, s[0] - i*h, s[n-1] - (n-1-i)*h}); ll high = min({maxl, s[0] + i*h, s[n-1] + (n-1-i)*h}); for (ll k = low; k <= high; k++){ treeseg[base+k] = dp[i-1][k]; } for (ll k = base-1; k > 0; k--){ treeseg[k] = min(treeseg[2*k], treeseg[2*k+1]); } for (ll j = low; j <= high; j++){ ll l = max(low, j-h), r = min(high, j+h); dp[i][j] = rangemin(l, r) + abs(j-s[i]); } } ll low = max({0LL, s[0] - (n-1)*h, s[n-1]}); ll high = min({maxl, s[0] + (n-1)*h, s[n-1]}); ll ans = 1e18; for (ll i = low; i <= high; i++) ans = min(ans, dp[n-1][i]); pr(ans); }