AT_agc044_e [AGC044E] Random Pawn

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

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