Problem:
 Score : 600 points    Problem Statement There are N cities in Republic of AtCoder. The size of the i -th city is A_{i} .
Takahashi would like to build N-1 bidirectional roads connecting two cities so that any city can be reached from any other city by using these roads.  Assume that the cost of building a road connecting the i -th city and the j -th city is |i-j| \times D + A_{i} + A_{j} .
For Takahashi, find the minimum possible total cost to achieve the objective.      Constraints  1 \leq N \leq 2 \times 10^5  1 \leq D \leq 10^9  1 \leq A_{i} \leq 10^9  A_{i} and D are integers.         Input Input is given from Standard Input in the following format:  N  D  A_1  A_2  ...  A_N       Output Print the minimum possible total cost.        Sample Input 1 3 1
1 100 1      Sample Output 1 106  This cost can be achieved by, for example, building roads connecting City 1 , 2 and City 1 , 3 .       Sample Input 2 3 1000
1 100 1      Sample Output 2 2202       Sample Input 3 6 14
25 171 7 1 17 162      Sample Output 3 497       Sample Input 4 12 5
43 94 27 3 69 99 56 25 8 15 46 8      Sample Output 4 658

Solution (Python):
def main():
    import sys
    from collections import defaultdict
    input = sys.stdin.readline

    class UnionFind():
        def __init__(self, n):
            self.n = n
            self.root = [-1] * (n + 1)
            self.rnk = [0] * (n + 1)

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

        def unite(self, x, y):
            x = self.find_root(x)
            y = self.find_root(y)
            if x == y:
                return
            elif self.rnk[x] > self.rnk[y]:
                self.root[x] += self.root[y]
                self.root[y] = x
            else:
                self.root[y] += self.root[x]
                self.root[x] = y
                if self.rnk[x] == self.rnk[y]:
                    self.rnk[y] += 1

        def isSameGroup(self, x, y):
            return self.find_root(x) == self.find_root(y)

        def size(self, x):
            return -self.root[self.find_root(x)]

    class Bit:
        def __init__(self, n):
            self.size = n
            self.inf = 10 ** 15
            self.tree = [self.inf] * (n + 1)

        def query(self, i):
            s = self.inf
            while i > 0:
                s = min(self.tree[i], s)
                i -= i & -i
            return s

        def update(self, i, x):
            while i <= self.size:
                self.tree[i] = min(self.tree[i], x)
                i += i & -i

    N, D = map(int, input().split())
    A = list(map(int, input().split()))

    tmp = [(a, i+1) for i, a in enumerate(A)]
    tmp.sort(key=lambda x: x[0])
    segtree_plus = Bit(N+5)
    segtree_minus = Bit(N+5)
    edge = []
    val2idx_plus = defaultdict(int)
    val2idx_minus = defaultdict(lambda: N+3)
    edge_append = edge.append
    inf = 10**15
    for a, i in tmp:
        val_plus = a+D*i
        val_minus = a-D*i
        segtree_plus.update(N+1-i, val_plus)
        segtree_minus.update(i, val_minus)
        i_ori = val2idx_plus[val_plus]
        if i > i_ori:
            val2idx_plus[val_plus] = i
        i_ori = val2idx_minus[val_minus]
        if i < i_ori:
            val2idx_minus[val_minus] = i
        plus_min = segtree_plus.query(N-i)
        if plus_min < inf:
            j_plus = val2idx_plus[plus_min]
            edge_append((i, j_plus, A[i-1] + A[j_plus-1] + D*(j_plus - i)))
        minus_min = segtree_minus.query(i-1)
        if minus_min < inf:
            j_minus = val2idx_minus[minus_min]
            edge_append((i, j_minus, A[i-1] + A[j_minus-1] + D * (i - j_minus)))

    edge.sort(key=lambda x: x[2])
    UF = UnionFind(N + 1)
    ans = 0
    for u, v, cost in edge:
        if UF.isSameGroup(u, v):
            continue
        ans += cost
        UF.unite(u, v)
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

from heapq import heappush, heappop, heapify
from collections import defaultdict

"""
・最小値のある場所を調べる。左右にまたがる辺は結ばない。
・最小値の両隣は必ず最小値と結ぶ。
・結んだあと1点に縮約していく。
"""

N,D,*A = map(int,read().split())

A = [0] + A + [0] 


mask = (1<<32)-1
q = [(x<<32)+i for i,x in enumerate(A[1:-1],1)]
heapify(q)
removed = defaultdict(int)

cost = []
while q:
    while q:
        x = q[0]
        if not removed[x]:
            break
        heappop(q); removed[x] -= 1
    if not q:
        break
    x = heappop(q)
    val,ind = x>>32, x&mask
    L = A[ind-1]; R = A[ind+1]
    if L:
        cost.append(L+val+D)
        
        newL = val+D
        if L > newL:
            A[ind-1] = newL
            removed[(L<<32)+(ind-1)] += 1
            heappush(q,(newL<<32)+(ind-1))
    if R:
        cost.append(R+val+D)
        
        newR = val+D
        if R > newR:
            A[ind+1] = newR
            removed[(R<<32)+(ind+1)] += 1
            heappush(q,(newR<<32)+(ind+1))
    A[ind] = 0

answer = sum(cost)
print(answer)

Solution (Python):
from operator import itemgetter
import itertools
def inpl(): return list(map(int, input().split()))
def cost(x, y):
    if x == y:
        return float('inf')
    return D * abs(x - y) + A[x] + A[y]
N, D = inpl()
A = inpl()
Right = [(v - i*D, i) for i, v in enumerate(A)]
Left = [(v + i*D, i) for i, v in enumerate(A)][::-1]
Right = list(map(itemgetter(1), itertools.accumulate(Right, min)))
Left = list(map(itemgetter(1), itertools.accumulate(Left, min)))[::-1]
ans = 0
hub = []
for i, (l, r) in enumerate(zip(Left, Right)) :
    if i == l == r:
        hub.append(i)
    else:
        ans += min(cost(i, r), cost(i, l))
print(ans + sum([cost(i, j) for i, j in zip(hub, hub[1:])]))

Solution (Python):
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)

Solution (Python):

N, D = map(int, input().split())
A_list = list(map(int, input().split()))



res = 0


B_list = [0]*N
for i in range(N):
    B_list[i] = A_list[i] + D*i
    
C_list = [0]*N
for i in range(N):
    C_list[i] = A_list[i] + D*(N-i)
    

B_cummmin = [0]*N
R = B_list[N-1]
BA = N-1
for i in range(N-1, -1, -1):
    if B_list[i] <= R:
        R = B_list[i]
        BA = i
    B_cummmin[i] = BA


C_cummmin = [0]*N
R = C_list[0]
CA = 0
for i in range(N):
    if C_list[i] <= R:
        R = C_list[i]
        CA = i
    C_cummmin[i] = CA


start = 0
while start < N-1:
    end = B_cummmin[start+1]
    target = C_cummmin[start]
    res += D*(end - target) + A_list[target] + A_list[end]
    for i in range(start+1, end):
        ds = D*(i - target) + A_list[target] + A_list[i]
        de = D*(end - i) + A_list[end] + A_list[i]
        res += min(ds, de)
    start = end

print(res)