AT_arc138_c [ARC138C] Rotate and Play Game

有 $N$ 张卡牌，编号从 $1$ 到 $N$，第 $i$ 张牌上写有数字 $A_i$。本题中 $N$ 为偶数。 Snuke 和 Min 先生将要玩一个游戏。游戏有 $N$ 轮，两人交替操作，Snuke 先手。玩家进行以下操作。 - Snuke 的回合：他可以选择拿走任意一张没有被拿走的卡牌。 - Min 先生的回合：他会拿走**编号**最小的没有被拿走的卡牌。 Snuke 的得分是他拿走的牌上写的数字之和。Snuke 会用最优策略进行游戏来最大化他的得分。 碰巧，作为 Snuke 的一个大粉丝，你打算下黑手来最大化 Snuke 的得分。游戏开始前，你将执行以下操作一次： - 选择一个整数 $k(0\le k\le N -1)$，然后循环左移卡牌上的数字 $k$ 的距离。也就是说，卡牌 $1,2,\cdots,N$ 上将依次写有 $A_{k+1},A_{k+2},\cdots,A_N,A_1,\cdots,A_k$。 找出最大化得分的 $k$的值，还有选择此 $k$ 时的得分。

第一行一个整数 $N(2\le n\le 2\times 10^5)$。保证 $N$ 是偶数。 第二行 $N$ 个整数 $A_1,A_2,\cdots,A_N(1\le A_i\le 10^9)$。

输出一行两个整数。第一个整数 $k(0\le k\le N-1)$ 表示你选择的整数，第二个整数 $s$ 表示此时的得分。如果有多种 $k$ 可以最大化 $s$，输出任意一种均可。

**样例 1 解释** 如果你选择 $k=1$，卡牌 $1,2,3,4$ 上将分别写有 $4,1,2,3$。游戏进行过程如下。 - Snuke 拿走卡牌 $1$。 - Min 先生拿走卡牌 $2$。 - Snuke 拿走卡牌 $4$。 - Min 先生拿走卡牌 $3$。 此情况下，Snuke 的得分为 $7$。 对于此输入，$k=2,3$ 同样为正确答案。