题面

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$

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