题目描述

$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$ を選んだ場合のスコアを求めてください．

输入格式

入力は以下の形式で標準入力から与えられる．

$N$ $A_1$ $A_2$ $\cdots$ $A_N$

输出格式

以下の形式で答えを出力せよ．

$k$ $s$

ここで $k$ はあなたが選ぶ整数 ($0\ \leq\ k\ \leq\ N-1$) であり，$s$ はその $k$ を選んだ場合のスコアである． なお，$s$ を最大化するような $k$ が複数存在する場合，どれを出力しても正解とみなされる．

题目大意

题面

A 与 B 在玩游戏，其中 A 先手。

有 $n$ 个数 $a_1-a_n$，A 每次可以任意取一个数，B 每次会取没有被取的数中下标最小的一数。

A 想最大化自己拿到的数字和。他可以选择一个数字 $k \in [0,n)$，把第 $1$ 至第 $k$ 个数依次提到数组的最后面，来实现他的目的。$k=0$ 时，相当于不做操作。

输入 $n$ 和 $a$ 数组，请输出 $k$，和 A 拿到的数字和。如果有多个 $k$，输出任一即可。

数据范围

• $1 \leq n \leq 2 \cdot 10^5$
• $2 \mid n$
• $1\leq a_i \leq 10^9$

样例解释 #1

选择 $k=1,2,3$ 均可，答案为 $7$。

以 $k=1$ 为例，数组将变为 $4,1,2,3$。之后执行以下过程：

• A 取走 $4$
• B 取走 $1$
• A 取走 $3$
• B 取走 $2$

注意这里说的是数值不是下标。

4
3 4 1 2

1 7

2
1 1

0 1

10
716893678 779607519 555600775 393111963 950925400 636571379 912411962 44228139 15366410 2063694

7 3996409938

提示

制約

• $2\ \leq\ N\ \leq\ 2\ \times\ 10^5$
• $N$ は偶数
• $1\ \leq\ A_i\ \leq\ 10^9$
• 入力される値はすべて整数

Sample Explanation 1

$k=1$ を選ぶと，カード $1,2,3,4$ に書かれた整数は $4,1,2,3$ になります． その後，ゲームは以下のように進行します． - すぬけ君がカード $1$ を取る． - 最小太郎君がカード $2$ を取る． - すぬけ君がカード $4$ を取る． - 最小太郎君がカード $3$ を取る． このときのすぬけ君のスコアは $7$ になります． なお，この例では $k=2,3$ でも正解になります．