DSequence (Hard version)

<Phiên bản khó hơn của bài DSequence>

Trong một lần dạo chơi tại vương quốc Coo.Land, Azerious quyết định tham gia vào cuộc thi giải đố của giáo sư Zaci. Câu đố mà Azerious nhận được có đề bài như sau: Cho một dãy số nguyên a có độ dài n và một số nguyên d cho trước. Mỗi lượt người chơi được chọn một số nguyên trong dãy và được phép tăng hoặc giảm số nguyên đó đi 1 đơn vị. Tính toán xem số lượt chơi ít nhất mà người chơi phải thực hiện để đưa dãy về dạng sau: 

• a[1] = a[0] + d 
• a[2] = a[1] + d
• a[3] = a[2] + d
• .......
• a[n-1] = a[n-2] + d

Hãy giúp Azerious giải câu đố của Zaci. 

Ví dụ:

• Với d = 2, a = [1,3,7,3] thì minCost(d, a) = 6
  Giải thích: Các lượt chơi mà azerious sẽ thực hiện như sau: 
  • Lượt 1: Giảm a[2] đi 1 đơn vị
  • Lượt 2: Tăng a[3] thêm 1 đơn vị
  • Lượt 3: Tăng a[3] thêm 1 đơn vị
  • Lượt 4: Tăng a[3] thêm 1 đơn vị
  • Lượt 5: Giảm a[2] đi 1 đơn vị 
  • Lượt 6: Tăng a[3] thêm 1 đơn vị

Đầu ra/Đầu vào

• [Giới hạn thời gian chạy] 0.5s với C++, 3s với Java/C#, 4s với Python,Js, Go
• [Đầu vào]: integer
  d <= 109 
• [Đầu vào]: array.integer
  1 <= a.size() <= 100000
-107 <= a[i] <= 107
• [Đầu ra]: long long
  Số lượt chơi ít nhất mà Azerious phải thực hiện