問題文

あなたは大人気ゲーム 「スペースエクスプローラー高橋君」 で遊んでいます。 このゲームの目的は宇宙船すぬけ号の艦長である高橋君となって、宇宙一の探検家を目指すことです。 現在あなたは 宇宙で一番おいしいりんご が宙域 RNG-58 にあることを突き止め、 RNG-58 へ向かっています。
宇宙で一番おいしいりんごは宇宙一おいしいので、宇宙海賊の青木君がすぬけ号を狙ってやってきました。 青木君は宇宙船けぬす号(すぬけ号の同型艦です)の艦長であり、高橋君のライバルです。 すぬけ号に取り付けられたすぬけキャノンでけぬす号を撃破しましょう！

けぬす号は 1 番から N 番までの番号がついた N ヶ所の区画からなり、区画 i の防御力は a_i です。 すぬけ号に取り付けられたすぬけキャノンは N 門あり、1 番から N 番までの番号がついています。 i 番のすぬけキャノンでけぬす号の区画 j を破壊するには a_j + (j-i)^{2} だけエネルギーを消費します。

どこか 1 つの区画を破壊すればけぬす号を撃破可能ですが、あなたは今後の航行のためにもなるべくすぬけ号のエネルギーを温存したいです。 それぞれのすぬけキャノンについて、けぬす号を撃破するのに最小限必要なエネルギーを求めてください。

制約

• 1 \leq N \leq 2 \times 10^5
• 1 \leq a_i \leq 10^{12}
• 入力はすべて整数である

入力例 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