### PROBLEM LINK:

**Author:** Malvika Joshi

**Tester:** Sameer Gulati, Anurag Anand, Vaibhav Gosain

### DIFFICULTY:

Medium

### PREREQUISITES:

Greedy Algorithms

### PROBLEM:

There are N towns in a line. Distance between town i and j is abs(j-i). We want to go from town 0 to town N-1. From town i, we can jump to any town j > i and that costs (j-i)*A[i] + (j^{2} - i^{2})*A[i]^{2}, where A is given as input. We want to find the minimum cost needed. N <= 10^5.

### EXPLANATION:

If you write cost function for path i->j->k and compare it with the cost function for path i->k you can see that the former is better (costs less energy) if and only if either |A[j]| < |A[i]| or |A[j]| = |A[i]| with A[i]>0.

From this observation it is quite easy to see that the optimal path would be greedy jumping from 0 to first i such that |A[i]| < |A[0]| or A[i] = -A[0] (if A[0]>0) or directly to n-1 if there is no such i and then doing the same for i till we reach n - 1. Jumping greedily to n-1 solves the problem with O(N) complexity.

Credits : http://codeforces.com/blog/entry/47485?#comment-318760

Time Complexity: O(N)

### TESTERâ€™S SOLUTION:

Testerâ€™s solution can be found here.