def kruskal(v_count: int, edges: list) -> int:
    """
    :param v_count: 頂点数
    :param edges: [(weight, from, to), ... ]
    """
    from itertools import islice
    tree = [-1]*v_count

    def get_root(x) -> int:
        if tree[x] < 0:
            return x
        tree[x] = get_root(tree[x])
        return tree[x]

    def unite(a) -> bool:
        x, y = get_root(a[1]), get_root(a[2])
        if x != y:
            big, small = (x, y) if tree[x] < tree[y] else (y, x)
            tree[big] += tree[small]
            tree[small] = big
        return x != y

    cost = 0
    for w, _s, _t in islice(filter(unite, sorted(edges)), v_count-1):
        cost += w
    return cost


class BIT():
    def __init__(self, number):
        self.n = number
        self.list = [10 ** 22] * (number + 1)

    def add(self, i, x):  # ith added x  1indexed
        while i <= self.n:
            self.list[i] = min(x, self.list[i])
            i += i & -i

    def search(self, i):  # 1-i min
        s = 10 ** 22
        while i > 0:
            s = min(s, self.list[i])
            i -= i & -i
        return s

import time
import random
start = time.clock()
      
N,D=2*10**5, random.randint(1,10**9)
A=[]
for _ in range(N):
    A.append(random.randint(1,10**9))
B=[(A[i],i) for i in range(N)]
B.sort()
table=[]
lbit=BIT(N)
rbit=BIT(N)
dl={}
dr={}

print("defined variables: {} sec".format(time.clock()-start))

for b,i in B:
    lbit.add(i+1,b+(N-1-i)*D)
    rbit.add(N-i,b+i*D)
    dl[b+(N-1-i)*D]=i
    dr[b+i*D]=i
    sl=lbit.search(i)
    sr=rbit.search(N-i-1)
    if sl<=10**21:
        y=dl[sl]
        table.append((A[i]+A[y]+D*abs(i-y),i,y))
    if sr<=10**21:
        y=dr[sr]
        table.append((A[i]+A[y]+D*abs(i-y),i,y))

print("collected edges: {} sec".format(time.clock()-start))

print(kruskal(N, table))

print("calculated minimum cost: {} sec".format(time.clock()-start))