问题描述

您正在玩热门游戏“太空探险者高桥君”。游戏的目标是成为太空船Snug号的舰长高桥君，成为最伟大的宇宙探险家。目前，您已经发现“宇宙中最美味的苹果”在宙域RNG-58中，并朝着RNG-58前进。

由于宇宙中最美味的苹果实在太好吃了，宇宙海盗青木君前来抢夺Snug号。青木君是宇宙船 Kennsu号（与Snug号相同型号）的舰长，是高桥君的竞争对手。让我们用Snug号上的Snug炮摧毁Kennsu号！

Kennsu号由编号从1到N的N个区块组成，区块i的防御力为ai。 Snug号上有N门Snug炮，编号从1到N。为了摧毁Kennsu号的区块j，需要消耗能量aj + (j-i)^2。

只需破坏一个区块即可摧毁Kennsu号，但您希望尽可能保留Snug号的能量以供以后航行使用。对于每个Snug炮，请计算摧毁Kennsu号所需的最少能量。

约束条件

• $1 \leq N \leq 2 \times 10^5$
• $1 \leq a_i \leq 10^{12}$
• 输入都是整数

输入

输入以以下格式从标准输入中给出。

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

输出

每行输出一个答案。第i行表示由第i门Snug炮摧毁Kennsu号所需的最少能量。

示例 1

3
1 3 2

输出示例 1

1
2
2

示例 2

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

输出示例 2

1
2
4
7
10
14
10
7
4
2
1

示例 3

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

输出示例 3

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