/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
N 枚のカードがあり，1 から N までの番号がついています． カード i には整数 A_i が書かれています． なお，ここで N は偶数です．
これから，すぬけ君と最小太郎君がゲームをします． ゲームは N ターンからなり，すぬけ君から始めて二人が交互にターンをプレイします． 各ターンでは，以下の操作を行います．
- すぬけ君のターン：まだ誰にも取られていないカードのうち，好きなものを一つ選び，取る．
- 最小太郎君のターン：まだ誰にも取られていないカードのうち，番号が最小のものを一つ選び，取る．
すぬけ君のスコアは，すぬけ君が取ったカードに書かれた整数の総和になります． すぬけ君はスコアを最大化するように最適に行動します．
ところで，すぬけ君の大ファンであるあなたは，とある不正を行うことでスコアを最大化しようと考えています． 具体的には，ゲームの開始前に，あなたは以下の行動を一回行います．
- 整数 k (0 \leq k \leq N-1) を選び，カードに書かれている整数を k 個左に cyclic-shift する． つまり，カード 1,2,\cdots,N に書かれている数を，A_{k+1},A_{k+2},\cdots,A_N,A_1,\cdots,A_k に置き換える．
スコアを最大化するためにあなたが選ぶべき k の値，およびその k を選んだ場合のスコアを求めてください．
制約
- 2 \leq N \leq 2 \times 10^5
- N は偶数
- 1 \leq A_i \leq 10^9
- 入力される値はすべて整数
入力
入力は以下の形式で標準入力から与えられる．
N A_1 A_2 \cdots A_N
出力
以下の形式で答えを出力せよ．
k s
ここで k はあなたが選ぶ整数 (0 \leq k \leq N-1) であり，s はその k を選んだ場合のスコアである． なお，s を最大化するような k が複数存在する場合，どれを出力しても正解とみなされる．
入力例 1
4 3 4 1 2
出力例 1
1 7
k=1 を選ぶと，カード 1,2,3,4 に書かれた整数は 4,1,2,3 になります． その後，ゲームは以下のように進行します．
- すぬけ君がカード 1 を取る．
- 最小太郎君がカード 2 を取る．
- すぬけ君がカード 4 を取る．
- 最小太郎君がカード 3 を取る．
このときのすぬけ君のスコアは 7 になります．
なお，この例では k=2,3 でも正解になります．
入力例 2
2 1 1
出力例 2
0 1
入力例 3
10 716893678 779607519 555600775 393111963 950925400 636571379 912411962 44228139 15366410 2063694
出力例 3
7 3996409938
Score : 600 points
Problem Statement
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 two players, with Snuke going first. In each turn, the player does the following operation.
- In Snuke's turn: He takes any card of his choice that is not taken by anyone yet.
- In Mr. Min's turn: He takes the card with the minimum index that is not taken by anyone yet.
Snuke's score will be the sum of the integers written on the cards taken by Snuke. Snuke plays optimally to maximize the score.
Incidentally, 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.
- 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.
Find the value k that you should choose to maximize the score, and the resulting score when choosing that k.
Constraints
- 2 \leq N \leq 2 \times 10^5
- N is even.
- 1 \leq A_i \leq 10^9
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N A_1 A_2 \cdots A_N
Output
Print the answer in the following format:
k s
Here, k is the integer you choose (0 \leq k \leq N-1), and s is the score when choosing that k. If there are multiple values of k that maximize s, printing any of them will be accepted.
Sample Input 1
4 3 4 1 2
Sample Output 1
1 7
If 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.
- Snuke takes Card 1.
- Mr. Min takes Card 2.
- Snuke takes Card 4.
- Mr. Min takes Card 3.
In this case, Snuke's score is 7.
In this input, k=2,3 will also be accepted.
Sample Input 2
2 1 1
Sample Output 2
0 1
Sample Input 3
10 716893678 779607519 555600775 393111963 950925400 636571379 912411962 44228139 15366410 2063694
Sample Output 3
7 3996409938