{"trustable":true,"prependHtml":"\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS-MML_HTMLorMML\" type\u003d\"text/javascript\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv class\u003d\"panel_content\"\u003e\n 欢迎来到迦勒镇,这是一个围绕着滴水湖的高新技术产业开发区。沿湖有 N 个以 0 到 N - 1 编号的村庄,而环线公交是这个城镇唯一的交通工具。公交车是单向行驶线路,依次经过村庄 0, 1, 2, ... , N - 1, 然后返回第 0 号村庄,再继续以上路线。\n \u003cbr\u003e\n 我们可以用整数 $w_i$ 来衡量第 i 个村庄的景观,其中 $\\sum_{i\u003d0}^{N-1}$ $w_i$ \u003d 0。一旦旅行者从第 u 个村庄乘坐公交车到第 v 个村庄,他会根据两个系数 a \u003d $w_v$ 和 b \u003d w(s) 的和来评价这次经历。数据保证了和为 $b \\ge 0$。现在,作为导游,你需要为远道而来的客人设计一份旅行手册。你的任务是选择一个村庄作为旅行的起点,并至少再选择两个村庄。客人将从第 $i_0$ 个村庄开始旅行,按照公交车的路线依次游览计划好的 k 个村庄,最后从第 $i_0$ 个村庄回到第 $i_k$ 个村庄结束旅行。如果我们让 $i_{k+1} \u003d i_0$ ,整个旅行将由分数 $\\frac{1}{2} \\sum_{j\u003d0}^{k}(a_{i_{j+1}} - a_{i_j})\\frac{b_{i_{j}}b_{i_{j+1}}}{a_{i_{j}}a_{i_{j+1}}}$ 评估。对得分的负面影响要求是连续片段的总和。你需要找出可能的最大得分。\n\u003c/div\u003e"}},{"title":"输入","value":{"format":"HTML","content":"输入的第一行包含一个整数 t,表示测试用例的数量。然后是 t 个测试用例。对于每个测试用例,第一行包含一个整数 N (3 ≤ N ≤ 100000)。第二行包含 N 个非零整数\n\u003cbr\u003e\n$w_0$ 到 $w_{N-1}$ ,其中每个 $w_i$ 满足 $|w_i|$ ≤ 100。我们保证 $w_i$ 的总和为零。\n\u003cbr\u003e"}},{"title":"输出","value":{"format":"HTML","content":"对于每个测试用例,以小数点后 5 位四舍五入的形式在一行中输出整个评估的最大得分。"}},{"title":"示例","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e1\r\n10\r\n1 4 1 2 -3 -5 2 -2 2 -2\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e28.66667\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}},{"title":"提示","value":{"format":"HTML","content":"\u003cbr\u003e\n最佳路线从第 5 个村庄开始。依次经过第 6、7、8、9、0、1、2、3 号村庄,最后到达第 4 个村庄。然后沿湖前往第 3 号村庄。再次前往第 2 号村庄,最后返回第 5 号村庄。\n\u003cbr\u003e"}}]}