题目描述

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

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

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

输入格式

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

$N$ $A_1$ $A_2$ $\cdots$ $A_N$ $B_1$ $B_2$ $\cdots$ $B_N$

输出格式

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

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

题目大意

有一个圆排列，一开始的位置是随机的，每次可以选择继续或者不继续。继续的话需要花费 $b_p$ 的价值并会随机到达相邻的两边的一边，不继续的话就结束了并得到 $a_p$ 的价值。问最大的期望价值为多少。

• $n\leq 2\times 10^5,a_p\leq 10^{12},b_p\leq 100$

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

提示

制約

• $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$)
• 入力中のすべての値は整数である。