配点 : $1300$ 点

問題文

あなたの目的は、これからプレイするゲームでの利得の期待値を最大化することです。 ゲームを開始すると、ポーン (チェスの駒) が $\{1,2,\dots, N\}$ から等確率に選ばれた位置 $p$ に置かれます。これらの $N$ 個の位置 $1, 2, \dots, N$ は円周上に時計回りに並び、位置 $1$ の両隣は位置 $N, 2$ です。

ゲームはターン制で進行します。各ターンでは、ゲームを終えて $A_p$ ドル ($p$ はその時点でのポーンの位置) を得るか、$B_p$ ドルを支払ってゲームを続けるかを選べます。 ゲームを続ける場合、ポーンは自身と隣接する $2$ つの位置 $p-1$, $p+1$ のいずれかに等確率で移されます (位置 $0$ は位置 $N$ と、位置 $N+1$ は位置 $1$ とみなします)。

最適な戦略の期待利得は何ドルでしょうか。

注記: 「最適な戦略の期待利得」は、ゲームが 有限の ターン数で終わるような戦略における期待利得の上限と定義されます。

制約

• $2 \le N \le 200,000$
• $0 \le A_p \le 10^{12}$ ($p = 1,\ldots, N$)
• $0 \le B_p \le 100$ ($p = 1, \ldots, N$)
• 入力中のすべての値は整数である。

入力

入力は標準入力から以下の形式で与えられる。

$N$

$A_1$ $A_2$ $\cdots$ $A_N$

$B_1$ $B_2$ $\cdots$ $B_N$

出力

最適な戦略の期待利得を $1$ 個の実数として出力せよ。

出力された値は、絶対誤差または相対誤差が $10^{-10}$ を超えなければ正解とみなされる。

5
4 2 6 3 5
1 1 1 1 1

4.700000000000

4
100 0 100 0
0 100 0 100

50.000000000000

14
4839 5400 6231 5800 6001 5200 6350 7133 7986 8012 7537 7013 6477 5912
34 54 61 32 52 61 21 43 65 12 45 21 1 4

7047.142857142857

10
470606482521 533212137322 116718867454 746976621474 457112271419 815899162072 641324977314 88281100571 9231169966 455007126951
26 83 30 59 100 88 84 91 54 61

815899161079.400024414062