問題文

あなたの目的は、これからプレイするゲームでの利得の期待値を最大化することです。 ゲームを開始すると、ポーン (チェスの駒) が $\\{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}$ を超えなければ正解とみなされる。

入力例 1

5
4 2 6 3 5
1 1 1 1 1

出力例 1

4.700000000000

入力例 2

4
100 0 100 0
0 100 0 100

出力例 2

50.000000000000

入力例 3

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

出力例 3

7047.142857142857

入力例 4

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

出力例 4

815899161079.400024414062