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

```


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter, and the optional `goal` query parameter:

```
GET https://mayanktyagi3111.gitbook.io/interview-prep/greedy/save-energy.md?ask=<question>&goal=<endgoal>
```

`ask` is the immediate question: it should be specific, self-contained, and written in natural language.
`goal` is optional and describes the broader end goal you are ultimately trying to accomplish on behalf of the user. GitBook uses it to tailor the answer towards what is most useful for that goal.

The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.