题目描述

你的目标是在接下来要进行的游戏中最大化期望收益。当游戏开始时，棋子（象棋棋子）会以等概率被放置在 $\{1,2,\dots,N\}$ 中的某个位置 $p$。这 $N$ 个位置 $1,2,\dots,N$ 顺时针排列在圆周上，位置 $1$ 的相邻位置是 $N$ 和 $2$。

游戏以回合制进行。在每一回合，你可以选择结束游戏并获得 $A_p$ 美元（$p$ 是当前棋子的位置），或者支付 $B_p$ 美元继续游戏。如果选择继续游戏，棋子会以等概率移动到相邻的两个位置 $p-1$ 或 $p+1$（位置 $0$ 视为位置 $N$，位置 $N+1$ 视为位置 $1$）。

最优策略下的期望收益是多少美元？

注意：“最优策略下的期望收益”定义为在保证游戏在有限回合内结束的策略下，期望收益的上界。

输入格式

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

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

输出格式

请输出最优策略下的期望收益，输出一个实数。

只要输出的值与标准答案的绝对误差或相对误差不超过 $10^{-10}$，即可视为正确。

输入输出样例 #1

输入 #1

5
4 2 6 3 5
1 1 1 1 1

输出 #1

4.700000000000

输入输出样例 #2

输入 #2

4
100 0 100 0
0 100 0 100

输出 #2

50.000000000000

输入输出样例 #3

输入 #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

输入 #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

说明/提示

限制

• $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$）
• 输入中的所有数值均为整数。

由 ChatGPT 4.1 翻译