Problem Description

You are playing the popular game "Space Explorer Takahashi". The goal of this game is to become the best explorer in the universe as Captain Takahashi of the spaceship Snuke. Currently, you have discovered that the most delicious apple in the universe is located in the RNG-58 region, and you are heading towards it.
Since the most delicious apple in the universe is incredibly tasty, Aoki, the pirate, has come to target the Snuke. Aoki is the captain of the Kenus spaceship (a sister ship of the Snuke) and is Takahashi's rival. Use the Snuke Cannon installed on the Snuke to defeat the Kenus!

The Kenus consists of $ N $ compartments numbered from $ 1 $ to $ N $, and the defense strength of compartment $ i $ is $ a_i $. The Snuke is equipped with $ N $ Snuke Cannons numbered from $ 1 $ to $ N $. To destroy compartment $ j $ of the Kenus with the $ i $th Snuke Cannon, you need to consume $ a_j + (j-i)^2 $ energy.

Destroying any one compartment is enough to defeat the Kenus, but you want to conserve as much energy as possible for future voyages. For each Snuke Cannon, find the minimum energy required to defeat the Kenus.

Input Format

The input is given from the standard input in the following format:

$ N $ $ a_1 $ $ a_2 $ $ ... $ $ a_{N} $

Output Format

Output the answers in $ N $ lines. On the $ i $th line, output the minimum energy required to defeat the Kenus using the $ i $th Snuke Cannon.

Sample Input and Output

Sample Input #1

3
1 3 2

Sample Output #1

1
2
2

Sample Input #2

11
1 3 6 10 15 18 15 10 6 3 1

Sample Output #2

1
2
4
7
10
14
10
7
4
2
1

Sample Input #3

12
10 14 64 20 24 12 12 21 30 44 29 2

Sample Output #3

10
11
14
16
13
12
12
13
11
6
3
2

Notes/Hints

Constraints

• $1 \leq N \leq 2 \times 10^5$
• $1 \leq a_i \leq 10^{12}$
• All inputs are integers

见题面 Input 部分

见题面 Output 部分