{"problem":{"name":"[ICPC 2021 Nanjing R] Windblume Festival","description":{"content":"The Windblume Festival in Mondstadt is coming! People are preparing windblumes for Barbatos and for those they love and adore. The Windblume Festival is also an opportunity to improve the relationship","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":3000,"memory_limit":262144},"difficulty":{"LuoguStyle":"P3"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9852"},"statements":[{"statement_type":"Markdown","content":"The Windblume Festival in Mondstadt is coming! People are preparing windblumes for Barbatos and for those they love and adore. The Windblume Festival is also an opportunity to improve the relationships people have.\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/nbhhi3bg.png)\n\nDuring the festival, a famous game will be played every year, invented by Jean, the Acting Grand Master of the Knights of Favonius. In the game, $n$ players numbered from $1$ to $n$ stand in a circle, each holding an integer with them. Each turn, one player will be removed. The game will end when there is only one player left.\n\nFor each turn, let $k$ be the number of players remaining and $a_i$ be the integer player $i$ holds. Two adjacent players, $x$ and $(x \\bmod k + 1)$ are selected and player $(x \\bmod k + 1)$ is removed from the game. Player $x$'s integer will then change from $a_x$ to $(a_x - a_{x \\bmod k + 1})$. Player $y$ in this turn will become player $(y - 1)$ in the next turn for all $x < y \\le k$, though the integer they hold will not change.\n\nJean wants to know the maximum possible integer held by the last remaining player in the game by selecting the players in each round optimally.\n\n## Input\n\nThere are multiple test cases. The first line of the input contains one integer $T$ indicating the number of test cases. For each test case:\n\nThe first line contains one integer $n$ ($1 \\le n \\le 10^6$) indicating the initial number of players.\n\nThe next line contains $n$ integers $a_i$ ($-10^9 \\le a_i \\le 10^9$) where $a_i$ is the integer held by player $i$ at the beginning.\n\nIt is guaranteed that the sum of $n$ of all test cases will not exceed $10^6$.\n\n## Output\n\nFor each test case output one line containing one integer indicating the maximum possible integer.\n\n[samples]\n\n## Note\n\nFor the first sample test case follow the strategy shown below, where the underlined integers are the integers held by the players selected in each turn.\n\n$\\{\\underline{1}, -3, 2, \\underline{-4}\\}$ (select $x = 4$) $\\to$ $\\{-3, \\underline{2, -5}\\}$ (select $x = 2$) $\\to$ $\\{\\underline{-3, 7}\\}$ (select $x = 2$) $\\to$ $\\{10\\}$.","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9852","tags":["2021","Special Judge","O2优化","ICPC","南京"],"sample_group":[["5\n4\n1 -3 2 -4\n11\n91 66 73 71 32 83 72 79 84 33 93\n12\n91 66 73 71 32 83 72 79 84 33 33 93\n13\n91 66 73 71 32 83 72 79 84 33 33 33 93\n1\n0\n","10\n713\n746\n779\n0\n"]],"created_at":"2026-03-03 11:09:25"}}