配点 : 600 点
問題文
您正在玩流行游戏“太空探索者高桥君”。 这款游戏的目标是扮演 Snuke 飞船的船长 Takahashi,立志成为宇宙中最好的探险家。 目前你是 全宇宙最好吃的苹果 我们发现 位于 RNG-58 扇区并且正在前往 RNG-58。
宇宙中最好吃的苹果就是宇宙中最好吃的苹果,所以宇宙海盗青木君瞄准了 Snuke。 青木君是宇宙飞船 Kenusu(与 Snuke-gou 相同类型的飞船)的船长,也是高桥君的竞争对手。 让我们用 Snuke 附带的 Snuke 加农炮摧毁 Kenusu!
Kenusu 问题是 来自编号 1 编号至 N 编号为 编号 N 由 3 个部分组成; i 的防御力为 a_i 。 附在 Snuke 上的 Snuke 大炮 N 有一个门, 它们的编号最大为1 编号至 N 。 i Snuke Cannon Dekenusu 问题部分 摧毁 j 它仅消耗 a_j + (j-i)^{2} 能量。
某处 1 可以通过摧毁一部分来摧毁 Kenusu,但您希望为未来的航行保留尽可能多的能量。 对于每个 Snuke Cannon,找到摧毁 Kenusu 所需的最小能量。
制約
- 1 \leq N \leq 2 \times 10^5
- 1 \leq a_i \leq 10^{12}
- 所有输入均为整数
入力
输入是按以下格式从标准输入给出的。
N
a_1 a_2 ... a_{N}
出力
答案 行 N 行输出。i 在行 i 使用你的号码的潜核炮输出摧毁基努苏所需的最小能量。
入力例 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