问题描述

你正在玩一个游戏，你的目标是最大化你的预期收益。在游戏开始时，随机地把一个兵棋放在位置 $p\\in\\{1,2,\\dots, N\\}$ 上。这 $N$ 个位置排列成一个圆环（所以 $1$ 在 $N$ 和 $2$ 之间）。

游戏由回合组成。在每个回合中，你可以选择结束游戏并获得 $A_p$ 美元（其中 $p$ 是当前兵棋的位置），或者支付 $B_p$ 美元继续玩。如果你决定继续玩，兵棋会随机移动到相邻的两个位置 $p-1$、$p+1$（其中 $0 = N$ 且 $N+1=1$）。

最优策略的预期收益是多少？

注意："最优策略的预期收益" 定义为所有以有限次数回合结束的策略中的最大预期收益。

约束条件

• $2 \\le N \\le 200,000$
• 对于任意 $p = 1,\\ldots, N$，$0 \\le A_p \\le 10^{12}$
• 对于任意 $p = 1, \\ldots, N$，$0 \\le B_p \\le 100$
• 输入中的所有值都为整数。

输入

输入以以下格式从标准输入中给出：

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

输出

打印一个实数，最优策略的预期收益。如果相对或绝对误差不超过 $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