Problem Link : https://www.codechef.com/NCCW2021/problems/AKNTWRK

AK works in a logistics company, and he is assigned with a task to build a road network between N cities. The size of a city is Pi and AK would like to build N−1 bidirectional roads connecting two cities such that any city can reached from any other city.

Assuming that the cost of building a road between ith and jth city is abs(i−j)∗D+Pi+Pj. Find the minimum possible cost to achieve the task

Input:
The first line contains two integers N and D.
The second line contains the array P of size N.
Output:
Print the answer.

Constraints
1≤N≤2∗10^5
1≤D≤10^9
1≤Pi≤10^9
Sample Input:
3 1
1 100 1

Sample Output:
106

EXPLANATION:
This cost can be achieved by, for example, building roads connecting City 1,2 and City 1,3.

I was thinking in terms of some MST(Minimum Spanning tree) based approach to solve this problem but the complexity will be greater than O(NlogN). Not able to come up with some efficient approach for this problem.

Please suggest some optimal approach. Thanks in advance :)