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 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)
  
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"}]