{"raw_statement":[{"iden":"problem statement","content":"You are playing a game and your goal is to maximize your expected gain. At the beginning of the game, a pawn is put, uniformly at random, at a position $p\\in{1,2,\\dots, N}$. The $N$ positions are arranged on a circle (so that $1$ is between $N$ and $2$).\nThe game consists of turns. At each turn you can either end the game, and get $A_p$ dollars (where $p$ is the current position of the pawn), or pay $B_p$ dollar to keep playing. If you decide to keep playing, the pawn is randomly moved to one of the two adjacent positions $p-1$, $p+1$ (with the identifications $0 = N$ and $N+1=1$).\nWhat is the expected gain of an optimal strategy?\n**Note**: The \"expected gain of an optimal strategy\" shall be defined as the supremum of the expected gain among all strategies such that the game ends in a _finite_ number of turns."},{"iden":"constraints","content":"*   $2 \\le N \\le 200,000$\n*   $0 \\le A_p \\le 10^{12}$ for any $p = 1,\\ldots, N$\n*   $0 \\le B_p \\le 100$ for any $p = 1, \\ldots, N$\n*   All values in input are integers."},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$N$\n$A_1$ $A_2$ $\\cdots$ $A_N$\n$B_1$ $B_2$ $\\cdots$ $B_N$"},{"iden":"sample input 1","content":"5\n4 2 6 3 5\n1 1 1 1 1"},{"iden":"sample output 1","content":"4.700000000000"},{"iden":"sample input 2","content":"4\n100 0 100 0\n0 100 0 100"},{"iden":"sample output 2","content":"50.000000000000"},{"iden":"sample input 3","content":"14\n4839 5400 6231 5800 6001 5200 6350 7133 7986 8012 7537 7013 6477 5912\n34 54 61 32 52 61 21 43 65 12 45 21 1 4"},{"iden":"sample output 3","content":"7047.142857142857"},{"iden":"sample input 4","content":"10\n470606482521 533212137322 116718867454 746976621474 457112271419 815899162072 641324977314 88281100571 9231169966 455007126951\n26 83 30 59 100 88 84 91 54 61"},{"iden":"sample output 4","content":"815899161079.400024414062"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}