Please solve in Java or C$++,$ thank you. :$)$

Farmer John has $N(1N2*{10}^5)$ patches of grass in a line, where patch i has a level of bacteria that differs by $a_i$ from that

of healthy grass $(-{10}^{15}{a}_i{10}^{15}).$ For example, if $a_i=-3,$ then patch i has a level of bacteria $3$ lower than normal, and would

need exactly $3$ additional units of bacteria added to raise it to the point where it is considered healthy.

Farmer John wants to ensure every patch of grass is corrected to have a healthy level of bacteria. Conveniently, he owns two

brands of pesticide that he can spray on his field, one that adds bacteria and one that removes bacteria. When Farmer John

sprays either type of pesticide, he stands in patch $N($the rightmost patch$)$ and selects a power level $L$ for his sprayer $($

$1LN.$

The sprayer has the most impact on patches near Farmer John, with diminishing effect farther away. If Farmer John chooses the

pesticide that adds bacteria, then $L$ units of bacteria will be added to patch $N,L-1$ units to patch $N-1,L-2$ units to patch

$N-2,$ and so on$.$ Patches $1$dotsN$-L$ will receive no bacteria, since the sprayer isn't set to a level powerful enough to reach

them. Similarly, if Farmer John chooses the pesticide that removes bacteria, then $L$ units of bacteria will be removed from patch

$N,L-1$ units will be removed from patch $N-1,$ and so on$.$ Again, patches $1$dotsN$-L$ will be unaffected.

Find the minimum number of times Farmer John has to apply his sprayer such that every patch of grass has the recommended

value of bacteria for healthy grass. It is guaranteed that the answer is at most ${10}^9.$

Note that the large size of integers involved in this problem may require the use of $64-$bit integer data types $($e$.$g$.,$ a

"long long" in $\frac{C}{C}++.$

INPUT FORMAT $($input arrives from the terminal $/$ stdin$)$:

The first line contains $N.$

The second line contains $N$ integers $a_{1}dots{a}_N,$ the initial bacteria levels of each patch of grass.

OUTPUT FORMAT $($print output to the terminal $/$ stdout$)$:

The minimum number of applications necessary to make every patch of grass have the recommended value of bacteria for

healthy grass.

SAMPLE INPUT:

$2$

$-13$

SAMPLE OUTPUT:

$6$

Use the type of pesticide that removes bacteria, at a power level of $1,$ five times. Then use the type of pesticide that adds

bacteria, with a power level of $2,$ one time.

SAMPLE INPUT:

$5$

$1,3,-2,-7,5$

SAMPLE OUTPUT:

$26$

SCORING:

Inputs $3-5$: $N{10}^3,$ the answer is at most ${10}^3$

Inputs $6-10$: $N{10}^3$

Inputs $11-15$: No additional constraints.