output_description: Print the minimum possible total cost.
  
  * * *
input_description: Input is given from Standard Input in the following format:
  
      
      
      N D
      A_1 A_2 ... A_N
attempt: import sys
  from collections import defaultdict as dd
  
  input = sys.stdin.readline
  N, D = map(int, input().split())
  a = list(map(int, input().split()))
  dl = [0] * N
  dr = [0] * N
  base = 10**6
  for i in range(N):
      dl[i] = ((N - i) * D + a[i]) * base + i
      dr[i] = (i * D + a[i]) * base + i
  e = dd(list)
  
  
  class SegTree:
      def segfunc(self, x, y):
          return min(x, y)
  
      def __init__(self, n, ide_ele, init_val):
          #####単位元######
          self.ide_ele = ide_ele
          # num:n以上の最小の2のべき乗
          self.num = 2 ** (n - 1).bit_length()
          self.seg = [self.ide_ele] * 2 * self.num
          # set_val
          for i in range(n):
              self.seg[i + self.num - 1] = init_val[i]
          # built
          for i in range(self.num - 2, -1, -1):
              self.seg[i] = self.segfunc(self.seg[2 * i + 1], self.seg[2 * i + 2])
  
      def update(self, k, x):
          k += self.num - 1
          self.seg[k] = x
          while k + 1:
              k = (k - 1) // 2
              self.seg[k] = self.segfunc(self.seg[k * 2 + 1], self.seg[k * 2 + 2])
  
      def query(self, p, q):
          if q <= p:
              return self.ide_ele
          p += self.num - 1
          q += self.num - 2
          res = self.ide_ele
          while q - p > 1:
              if p & 1 == 0:
                  res = self.segfunc(res, self.seg[p])
              if q & 1 == 1:
                  res = self.segfunc(res, self.seg[q])
                  q -= 1
              p = p // 2
              q = (q - 1) // 2
          if p == q:
              res = self.segfunc(res, self.seg[p])
          else:
              res = self.segfunc(self.segfunc(res, self.seg[p]), self.seg[q])
          return res
  
  
  lseg = SegTree(N, pow(10, 20), dl)
  rseg = SegTree(N, pow(10, 20), dr)
  for i in range(N):
      l = lseg.query(0, i)
      r = rseg.query(i + 1, N)
      e[i].append((l % base, a[i] + l // base - D * (N - i)))
      e[l % base].append((i, a[i] + l // base - D * (N - i)))
      e[i].append((r % base, a[i] + r // base - D * i))
      e[r % base].append((i, a[i] + r // base - D * i))
  import heapq
  
  
  class prim:
      def __init__(self, n, e):
          self.e = e
          self.n = n
  
      def MSTcost(self):
          h = []
          visited = [0] * (self.n + 1)
          ks = list(self.e.keys())
          b = pow(10, 6)
          for edge in self.e[ks[0]]:
              heapq.heappush(h, edge[1] * b + edge[0])
          res = 0
          visited[ks[0]] = 1
          while len(h):
              p = heapq.heappop(h)
              p0 = p // b
              p1 = p % b
              if visited[p1]:
                  continue
              visited[p1] = 1
              for q in self.e[p1]:
                  if visited[q[0]]:
                      continue
                  heapq.heappush(h, q[1] * b + q[0])
              res += p0
          return res
  
  
  # print(e)
  pri = prim(N, e)
  print(pri.MSTcost())
  
problem_description: 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.
samples: [{"input": "3 1\n    1 100 1", "output": "106\n    \n\nThis cost can be achieved by, for example, building roads connecting City 1, 2\nand City 1, 3.\n\n* * *"}, {"input": "3 1000\n    1 100 1", "output": "2202\n    \n\n* * *"}, {"input": "6 14\n    25 171 7 1 17 162", "output": "497\n    \n\n* * *"}, {"input": "12 5\n    43 94 27 3 69 99 56 25 8 15 46 8", "output": "658"}]