#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
// Function to set up fast I/O
void setup_io() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
}
// Solves the L1 Isotonic Regression problem for a non-decreasing sequence using PAVA.
// It finds the optimal block partitions using L2 PAVA (mean-based), which is O(N),
// and then calculates the medians for each block to get the L1 solution.
std::vector<long long> compute_isotonic_nondecreasing(const std::vector<long long>& y) {
int n = y.size();
if (n == 0) {
return {};
}
// Active set for PAVA, stores pairs of (mean, weight) for each pool.
std::vector<std::pair<double, int>> pools;
for (long long val : y) {
pools.push_back({(double)val, 1});
// Merge pools as long as the non-decreasing property is violated.
while (pools.size() > 1 && pools.back().first < pools[pools.size() - 2].first) {
auto p2 = pools.back();
pools.pop_back();
auto p1 = pools.back();
pools.pop_back();
double merged_mean = (p1.first * p1.second + p2.first * p2.second) / (p1.second + p2.second);
int merged_weight = p1.second + p2.second;
pools.push_back({merged_mean, merged_weight});
}
}
// Reconstruct the final solution vector from the pools.
std::vector<long long> result(n);
int current_idx = 0;
for (const auto& pool : pools) {
int weight = pool.second;
// Create a temporary vector for the elements in the current block.
std::vector<long long> block_elements;
block_elements.reserve(weight);
for (int i = 0; i < weight; ++i) {
block_elements.push_back(y[current_idx + i]);
}
// Find the median of the block for the L1 solution.
std::nth_element(block_elements.begin(), block_elements.begin() + (weight - 1) / 2, block_elements.end());
long long median = block_elements[(weight - 1) / 2];
// Assign the median to all elements in this block.
for (int i = 0; i < weight; ++i) {
result[current_idx + i] = median;
}
current_idx += weight;
}
return result;
}
void solve() {
int n;
long long h;
std::cin >> n >> h;
std::vector<long long> s(n);
for (int i = 0; i < n; ++i) {
std::cin >> s[i];
}
// --- 1. Upper Bound Problem ---
// Transform S -> A such that we need a non-decreasing U'.
std::vector<long long> A(n);
for (int i = 0; i < n; ++i) {
A[i] = s[i] + (long long)i * h;
}
// Solve for the optimal non-decreasing U'.
std::vector<long long> U_prime = compute_isotonic_nondecreasing(A);
// Transform back to get the upper bound U on S'.
std::vector<long long> U(n);
for (int i = 0; i < n; ++i) {
U[i] = U_prime[i] - (long long)i * h;
}
// --- 2. Lower Bound Problem ---
// Transform S -> B such that we need a non-increasing L'.
std::vector<long long> B(n);
for (int i = 0; i < n; ++i) {
B[i] = s[i] - (long long)i * h;
}
// To find non-increasing L', solve for non-decreasing on -B and negate the result.
std::vector<long long> minus_B(n);
for (int i = 0; i < n; ++i) {
minus_B[i] = -B[i];
}
std::vector<long long> L_prime_neg = compute_isotonic_nondecreasing(minus_B);
// Transform back to get the lower bound L on S'.
std::vector<long long> L(n);
for (int i = 0; i < n; ++i) {
L[i] = -L_prime_neg[i] + (long long)i * h;
}
// --- 3. Calculate Final Cost ---
// The optimal S'[i] is the projection of S[i] onto the interval [L[i], U[i]].
long long total_cost = 0;
for (int i = 0; i < n; ++i) {
long long s_final_i = s[i];
if (s_final_i < L[i]) {
s_final_i = L[i];
}
if (s_final_i > U[i]) {
s_final_i = U[i];
}
total_cost += std::abs(s[i] - s_final_i);
}
std::cout << total_cost << std::endl;
}
int main() {
setup_io();
solve();
return 0;
}
