> For the complete documentation index, see [llms.txt](https://mayanktyagi3111.gitbook.io/interview-prep/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://mayanktyagi3111.gitbook.io/interview-prep/greedy/save-energy.md).

# 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, **i**th 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
```

```java
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;
    }
}

```