{"raw_statement":[{"iden":"problem statement","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$."},{"iden":"constraints","content":"*   $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."},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$N$\n$A_1$ $A_2$ $\\cdots$ $A_N$"},{"iden":"sample input 1","content":"4\n3 4 1 2"},{"iden":"sample output 1","content":"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."},{"iden":"sample input 2","content":"2\n1 1"},{"iden":"sample output 2","content":"0 1"},{"iden":"sample input 3","content":"10\n716893678 779607519 555600775 393111963 950925400 636571379 912411962 44228139 15366410 2063694"},{"iden":"sample output 3","content":"7 3996409938"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}