← 返回题目列表

AtCoder · colopl2018_final_c

C. 太空探索者高桥

中文机器翻译题面 查看原题

配点 : 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