Save Energy

There are N towns in a line, numbered from 0 to N - 1. Starting from town 0, we want to reach town N - 1. From town i, we can jump to any town j > i with an energy cost of (j-i)*A[i] + (j2 - i2)*A[i]2, where A[i] for all i are given in input. Find the minimum total energy cost to reach town N - 1 from town 0.

Input

The first line contains a single integer, N. The next line contains N space separated integers, ith integer denoting the value of A[i] , 0 ≤ i ≤ N - 1.

Output

Output the minimum cost to reach town N.

Constraints

• 1 ≤ N ≤ 10^5

• -10^3 ≤ A[i] ≤ 10^3

Example 1

Input:
5
1 -1 2 2 2

Output:
14

Example 2

Input:
4
2 2 3 4

Output:
42

class Codechef {
    // For choosing a stop in between (i & j) ,it needs to satisfy
    // fuel(i,k) + fuel(k,j) <= fuel(i,j), this futher solves to this :
    // A[j] + (k + j)*A[j]^2 <= A[i] + (k + j)*A[i]^2
    // This can be divied into 2 conditions :
    // 1) |A[i]| >= |A[k]| OR
    // 2) if( |A[i]| == |A[k]| ) => A[i] >= 0
    public static long saveEnergy(long[] arr, long n) {
        long cost = 0L;
        // Now the above equations were just a mathematical simplification
        // The core concept lies in how do we choose k
        // We will choose greedily, and choose the very first k satisfying the
        // conditions and then look forward to reduce
        // further by applying this between k and the end
        long i = 0;
        for (int k = 1; k < n - 1; k++) {
            if (Math.abs(arr[(int) i]) >= Math.abs(arr[k])) {
                if (Math.abs(arr[(int) i]) == Math.abs(arr[k])) {
                    if (arr[(int) i] >= 0) {
                        cost += (k * 1L - i) * arr[(int) i] + (k * k * 1L - i * i) * arr[(int) i] * arr[(int) i];
                        i = (long) k;
                    }
                } else {
                    cost += (k * 1L - i) * arr[(int) i] + (k * k * 1L - i * i) * arr[(int) i] * arr[(int) i];
                    i = (long) k;
                }
            }
        }
        cost += ((n - 1) - i) * arr[(int) i] + ((n - 1) * (n - 1) - i * i) * arr[(int) i] * arr[(int) i];
        return cost;
    }
}