{"problem":{"name":"Rotate and Play Game","description":{"content":"There are $N$ cards, indexed $1$ to $N$. Card $i$ has an integer $A_i$ written on it. Here, $N$ is even. Snuke and Mr. Min will play a game. The game consists of $N$ turns, alternately taken by the tw","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"arc138_c"},"statements":[{"statement_type":"Markdown","content":"There are $N$ cards, indexed $1$ to $N$. Card $i$ has an integer $A_i$ written on it. Here, $N$ is even.\nSnuke and Mr. Min will play a game. The game consists of $N$ turns, alternately taken by the two players, with Snuke going first. In each turn, the player does the following operation.\n\n*   In Snuke's turn: He takes any card of his choice that is not taken by anyone yet.\n*   In Mr. Min's turn: He takes the card with the minimum **index** that is not taken by anyone yet.\n\nSnuke's score will be the sum of the integers written on the cards taken by Snuke. Snuke plays optimally to maximize the score.\nIncidentally, being a big fan of Snuke, you are planning to do something nasty to maximize the score. Specifically, before the start of the game, you will do the following action once.\n\n*   Choose an integer $k$ ($0 \\leq k \\leq N-1$) and cyclically shift the integers written on the cards by $k$ to the left: the cards $1,2,\\cdots,N$ will have $A_{k+1},A_{k+2},\\cdots,A_N,A_1,\\cdots,A_k$ written on them.\n\nFind the value $k$ that you should choose to maximize the score, and the resulting score when choosing that $k$.\n\n## Constraints\n\n*   $2 \\leq N \\leq 2 \\times 10^5$\n*   $N$ is even.\n*   $1 \\leq A_i \\leq 10^9$\n*   All values in input are integers.\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$N$\n$A_1$ $A_2$ $\\cdots$ $A_N$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"arc138_c","tags":[],"sample_group":[["4\n3 4 1 2","1 7\n\nIf you choose $k=1$, the cards $1,2,3,4$ will have $4,1,2,3$ written on them. Then, the game will go as follows.\n\n*   Snuke takes Card $1$.\n*   Mr. Min takes Card $2$.\n*   Snuke takes Card $4$.\n*   Mr. Min takes Card $3$.\n\nIn this case, Snuke's score is $7$.\nIn this input, $k=2,3$ will also be accepted."],["2\n1 1","0 1"],["10\n716893678 779607519 555600775 393111963 950925400 636571379 912411962 44228139 15366410 2063694","7 3996409938"]],"created_at":"2026-03-03 11:01:13"}}