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: # from typing import Callable
  
  
  def connecting_cities(N: int, D: int, A: list) -> int:
      edges = select_edges(N, D, A)
      edges = sorted(edges, key=lambda x: x[2], reverse=True)
      print(edges)
  
      uft = UnionFindTree(N)
  
      count = 0
      while not len(edges) == 0:
          u, v, d = edges.pop()
  
          if not uft.same(u, v):
              uft.summarize(u, v)
              count += d
  
      return count
  
  
  def select_edges(N: int, D: int, A: list) -> list:
      INF = 1 << 32
      st_l = SegmentTree(N, lambda x, y: x if x[0] < y[0] else y, (INF, -1))
      st_r = SegmentTree(N, lambda x, y: x if x[0] < y[0] else y, (INF, -1))
      indexes_A = sorted([i for i in range(N)], key=lambda x: A[x])
  
      # edges = []
      for i in indexes_A:
          la, li = st_l.range(0, i)
          if la < INF and li != -1:
              # edges.append(
              yield (li, i, abs(i - li) * D + A[i] + A[li])  # )
  
          ra, ri = st_r.range(i, N)
          if ra < INF and ri != -1:
              # edges.append(
              yield (ri, i, abs(i - ri) * D + A[i] + A[ri])  # )
  
          st_l.update(i, (A[i] + (N - i) * D, i))
          st_r.update(i, (A[i] + i * D, i))
  
      # return edges
  
  
  class SegmentTree:
  
      # def __init__(self, size: int, op: Callable[[any, any], any], init: any = 0):
      def __init__(self, size, op, init):
          """initialize SegmentTree
          :param size: Size of tree. This must be natural number.
          :param op: Operator which compares two numbers. This function return the
                  representative value of two arguments.
          :param init: The initial value of element of tree.
          """
          if size < 1:
              raise Exception("size must be greater than 0 (actual = %d)" % size)
  
          self.__treesize = 1
          self.__init = init
          # tree size is the minimum number which is greater than or equal to
          # designed `size` and is power of 2.
          while self.__treesize < size:
              self.__treesize *= 2
  
          self.__size = self.__treesize
          self.__treesize = self.__treesize * 2 - 1
  
          self.__comp = op
  
          # initialize tree
          self.__tree = [init for _ in range(self.__treesize)]
  
      def range(self, l: int, r: int) -> int:
          """Returns the representative value in range [l, r)
          :param l: left value(include)
          :param r: right value(not include)
          :return: the representative value in range[l, r)
          """
          return self.__range(l, r, 0, 0, self.__size)
  
      def __range(self, l: int, r: int, k: int, kl: int, kr: int) -> int:
          """
          :param l: left value (include)
          :param r: right value (not include)
          :param k: node index
          :param kl: left value of node
          :param kr: right value of node
          """
          if kr <= l or r <= kl:
              # no crossing
              return self.__init
          if l <= kl and kr <= r:
              # including whole k's range
              return self.__tree[k]
  
          vl = self.__range(l, r, 2 * k + 1, kl, (kl + kr) // 2)
          vr = self.__range(l, r, 2 * k + 2, (kl + kr) // 2, kr)
          if vl is None:
              return vr
          if vr is None:
              return vl
  
          return self.__comp(vl, vr)
  
      def update(self, index: int, val: int):
          """update value at self.__tree[index]'s value"""
          index += self.__size - 1
          self.__tree[index] = val
  
          while index > 0:
              index = (index - 1) // 2
              self.__tree[index] = self.__comp(
                  self.__tree[2 * index + 1], self.__tree[2 * index + 2]
              )
  
      def print(self):
          """for debug"""
          print(self.__tree)
  
  
  class UnionFindTree:
  
      def __init__(self, size: int):
          """UnionFindTreeを初期化します
          :param size: サイズ
          :return: UnionFindTree
          """
          if size < 0:
              raise Exception("size must be greater than 0.")
  
          self.__parent = [-1] * size
  
      def summarize(self, a: int, b: int):
          """aを含む木とbを含む木をまとめます
          :param a: 木a
          :param b: 木b
          """
          a = self.__root(a)
          b = self.__root(b)
  
          if a != b:
              self.__parent[b] = a
  
      def __root(self, a: int) -> int:
          """aの根を求めます
          :param a: 木の要素
          :return: 根
          """
          if self.__parent[a] == -1:
              return a
          else:
              return self.__root(self.__parent[a])
  
      def same(self, a: int, b: int) -> bool:
          """a と b が同じ木に属するかを判断します
          :param a: 木
          :param b: 木
          :return: a と b が同じ木なら True。そうでないなら False。
          """
          return self.__root(a) == self.__root(b)
  
  
  if __name__ == "__main__":
      N, D = [int(s) for s in input().split()]
      A = [int(s) for s in input().split()]
      ans = connecting_cities(N, D, A)
      print(ans)
  
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"}]