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: def main():
      N, D = tuple(map(int, input().split()))
      A = tuple(map(int, input().split()))
  
      A2 = [[A[i], i, 0] for i in range(N)]
      A2.sort()
      for i in range(N):
          A2[i][2] = i
      A2.sort(key=lambda x: x[1])
      A2 = tuple(A2)
      rt = A[N - 1]
      Ll = [N - 1]
      k = N - 1
      for i in range(N - 2, 0, -1):
          t = A[i]
          if rt > t - (k - i) * D:
              Ll.append(i)
              k = i
              rt = t
  
      rt = A[0]
      Lr = [0]
      k = 0
      for i in range(1, N - 1):
          t = A[i]
          if rt > t + (k - i) * D:
              Lr.append(i)
              k = i
              rt = t
  
      Ll = tuple(Ll)
      Lr = tuple(Lr)
  
      L = []
      lC = -1
      rC = -1
      for i in range(N - 1):
          if i >= Ll[lC]:
              lC -= 1
          t = Ll[lC]
          if A2[i][2] > A2[t][2]:
              L.append((A[i] + A[t] + (t - i) * D, i, t))
          k = N - 1 - i
          if k <= Lr[rC]:
              rC -= 1
          t = Lr[rC]
          if A2[k][2] > A2[t][2]:
              L.append((A[k] + A[t] + (k - t) * D, t, k))
  
      L.sort()
  
      T = [i for i in range(N)]
      C = 0
      A = 0
      for i in L:
          xR = i[1]
          xC = 0
          yR = i[2]
          yC = 0
          while T[xR] != xR:
              xC += 1
              xR = T[xR]
          while T[yR] != yR:
              yC += 1
              yR = T[yR]
          if xR != yR:
              if xC < yC:
                  T[xR] = yR
              else:
                  T[yR] = xR
          if xR != yR:
              C += 1
              A += i[0]
              # print(i)
              if C == N - 1:
                  break
  
      print(A)
  
  
  main()
  
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"}]