Buggy python submission (verdict: Time Limit Exceeded):
class SegmentTree:

    def __init__(self, n, sentinel=0):
        n2 = 1 << (n - 1).bit_length()
        self.n = n2
        self.data = [sentinel] * ((n2 << 1) - 1)
        self.offset = n2 - 1

    def update(self, k, x):
        i = k + self.offset
        self.data[i] = x
        while i:
            p = (i - 1) // 2
            if self.data[p] > self.data[i]:
                self.data[p] = self.data[i]
            else:
                break
            i = p

    def get_left_min(self, k):
        i = k + self.offset - 1
        ret = self.data[i]
        while i:
            if i % 2 == 0:
                ret = min(ret, self.data[i - 1])
            i = (i - 1) // 2
        return ret

    def get_right_min(self, k):
        i = k + self.offset + 1
        ret = self.data[i]
        while i:
            if i % 2 == 1:
                ret = min(ret, self.data[i + 1])
            i = (i - 1) // 2
        return ret


class UnionFind:
    def __init__(self, n):
        self.table = [-1] * n

    def _root(self, x):
        if self.table[x] < 0:
            return x
        else:
            self.table[x] = self._root(self.table[x])
            return self.table[x]

    def find(self, x, y):
        return self._root(x) == self._root(y)

    def union(self, x, y):
        r1 = self._root(x)
        r2 = self._root(y)
        if r1 == r2:
            return
        d1 = self.table[r1]
        d2 = self.table[r2]
        if d1 <= d2:
            self.table[r2] = r1
            if d1 == d2:
                self.table[r1] -= 1
        else:
            self.table[r1] = r2


n, d = map(int, input().split())
aaa = list(map(int, input().split()))
seg_l = SegmentTree(n, (10 ** 10, -1))
seg_r = SegmentTree(n, (10 ** 10, -1))
bbb = sorted((a, i) for i, a in enumerate(aaa))
edges = set()

for a, i in bbb:
    cost_l = -i * d + a
    cost_r = i * d + a
    seg_l.update(i, (cost_l, i))
    seg_r.update(i, (cost_r, i))

    di = i * d
    if i > 0:
        base_cost, j = seg_l.get_left_min(i)
        if j > -1:
            edges.add((base_cost + di + a, j, i))
    if i < n - 1:
        base_cost, j = seg_r.get_right_min(i)
        if j > -1:
            edges.add((base_cost - di + a, i, j))

uft = UnionFind(n)
ans = 0
for c, i, j in sorted(edges):
    if uft.find(i, j):
        continue
    ans += c
    uft.union(i, j)

print(ans)


Fixed submission:
from itertools import accumulate
from operator import itemgetter

n, d = map(int, input().split())
aaa = list(map(int, input().split()))
costs_l = [(-i * d + a, i) for i, a in enumerate(aaa)]
costs_r = [(i * d + a, i) for i, a in enumerate(aaa)]

costs_l = list(accumulate(costs_l, min))
costs_r = list(accumulate(reversed(costs_r), min))
costs_r.reverse()

hubs = set(map(itemgetter(1), costs_l))
hubs.intersection_update(map(itemgetter(1), costs_r))
hubs.add(0)
hubs.add(n - 1)
hubs = sorted(hubs)

ans = sum(aaa) - aaa[-1]
s = hubs[0]
for t in hubs[1:]:
    cls = costs_l[s][0]
    crt = costs_r[t][0]
    ans += crt - s * d
    ans += sum(min(cls + i * d, crt - i * d) for i in range(s + 1, t))
    s = t
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
class SegmentTree:
    SENTINEL = (float('inf'), 0)

    def __init__(self, n):
        n2 = 1 << (n - 1).bit_length()
        self.n = n2
        self.data = [self.SENTINEL] * ((n2 << 1) - 1)
        self.offset = n2 - 1

    def create(self, aaa):
        s = self.offset
        t = s + len(aaa)
        self.data[s:t] = aaa
        for i in range(self.offset - 1, -1, -1):
            self.data[i] = min(self.data[i * 2 + 1], self.data[i * 2 + 2])

    def get_left_min(self, k):
        i = k + self.offset - 1
        ret = self.data[i]
        while i:
            if i % 2 == 0:
                ret = min(ret, self.data[i - 1])
            i = (i - 1) // 2
        return ret

    def get_right_min(self, k):
        i = k + self.offset + 1
        ret = self.data[i]
        while i:
            if i % 2 == 1:
                ret = min(ret, self.data[i + 1])
            i = (i - 1) // 2
        return ret


class UnionFind:
    def __init__(self, n):
        self.table = [-1] * n

    def _root(self, x):
        if self.table[x] < 0:
            return x
        else:
            self.table[x] = self._root(self.table[x])
            return self.table[x]

    def find(self, x, y):
        return self._root(x) == self._root(y)

    def union(self, x, y):
        r1 = self._root(x)
        r2 = self._root(y)
        if r1 == r2:
            return
        d1 = self.table[r1]
        d2 = self.table[r2]
        if d1 <= d2:
            self.table[r2] = r1
            if d1 == d2:
                self.table[r1] -= 1
        else:
            self.table[r1] = r2


n, d = map(int, input().split())
aaa = list(map(int, input().split()))
seg_l = SegmentTree(n)
seg_r = SegmentTree(n)
costs_l = [((i - n + 1) * d + a, n - i - 1) for i, a in enumerate(reversed(aaa))]
costs_r = [(i * d + a, i) for i, a in enumerate(aaa)]
costs_l.reverse()
seg_l.create(costs_l)
seg_r.create(costs_r)

edges = set()
nd = (n - 1) * d
for i, a in enumerate(aaa):
    di = i * d

    if i > 0:
        base_cost, j = seg_l.get_left_min(i)
        edges.add((base_cost + di + a, j, i))
    if i < n - 1:
        base_cost, j = seg_r.get_right_min(i)
        edges.add((base_cost - di + a, i, j))

uft = UnionFind(n)
ans = 0
for c, i, j in sorted(edges):
    if uft.find(i, j):
        continue
    ans += c
    uft.union(i, j)

print(ans)


Fixed submission:
from itertools import accumulate
from operator import itemgetter

n, d = map(int, input().split())
aaa = list(map(int, input().split()))
costs_l = [(-i * d + a, i) for i, a in enumerate(aaa)]
costs_r = [(i * d + a, i) for i, a in enumerate(aaa)]

costs_l = list(accumulate(costs_l, min))
costs_r = list(accumulate(reversed(costs_r), min))
costs_r.reverse()

hubs = set(map(itemgetter(1), costs_l))
hubs.intersection_update(map(itemgetter(1), costs_r))
hubs.add(0)
hubs.add(n - 1)
hubs = sorted(hubs)

ans = sum(aaa) - aaa[-1]
s = hubs[0]
for t in hubs[1:]:
    cls = costs_l[s][0]
    crt = costs_r[t][0]
    ans += crt - s * d
    ans += sum(min(cls + i * d, crt - i * d) for i in range(s + 1, t))
    s = t
print(ans)