Wonderful Jump solution codeforces

Wonderful Jump solution codeforces – You are given an array of positive integers 𝑎1,𝑎2,,𝑎𝑛a1,a2,…,an of length 𝑛n.

Wonderful Jump solution codeforces

In one operation you can jump from index 𝑖i to index 𝑗j (1𝑖𝑗𝑛1≤i≤j≤n) by paying min(𝑎𝑖,𝑎𝑖+1,,𝑎𝑗)(𝑗𝑖)2min(ai,ai+1,…,aj)⋅(j−i)2 eris.

For all 𝑘k from 11 to 𝑛n, find the minimum number of eris needed to get from index 11 to index 𝑘k.

Input

The first line contains a single integer 𝑛n (2𝑛41052≤n≤4⋅105).

The second line contains 𝑛n integers 𝑎1,𝑎2,𝑎𝑛a1,a2,…an (1𝑎𝑖𝑛1≤ai≤n).

Output

Output 𝑛n integers — the 𝑘k-th integer is the minimum number of eris needed to reach index 𝑘k if you start from index 11.

Wonderful Jump solution codeforces

input

Copy
3
2 1 3
output

Copy
0 1 2 

Wonderful Jump solution codeforces

Copy
6
1 4 1 6 3 2
output

Copy
0 1 2 3 6 8 
input

Copy
2
1 2
output

Copy
0 1 
input

Copy
4
1 4 4 4
output

Copy
0 1 4 8 

Wonderful Jump solution codeforces

In the first example:

  • From 11 to 11: the cost is 00,
  • From 11 to 22121→2 — the cost is min(2,1)(21)2=1min(2,1)⋅(2−1)2=1,
  • From 11 to 331231→2→3 — the cost is min(2,1)(21)2+min(1,3)(32)2=1+1=2min(2,1)⋅(2−1)2+min(1,3)⋅(3−2)2=1+1=2.

In the fourth example from 11 to 441341→3→4 — the cost is min(1,4,4)(31)2+min(4,4)(43)2=4+4=8min(1,4,4)⋅(3−1)2+min(4,4)⋅(4−3)2=4+4=8.

Also read: Partial Sorting solution codeforces

Leave a Reply

Your email address will not be published. Required fields are marked *