问题描述

有 $N$ 张卡片，索引从 $1$ 到 $N$。第 $i$ 张卡片上写有整数 $A_i$。其中，$N$ 是偶数。

Snuke 和 Mr. Min 将进行一场游戏。游戏由 $N$ 轮组成，由两名玩家交替进行，Snuke 先开始。在每一轮中，玩家执行以下操作：

• Snuke 的回合：他选择任意一张尚未被取走的卡片。
• Mr. Min 的回合：他选择当前尚未被取走的卡片中索引最小的那张。

Snuke 的得分将是他取走的卡片上整数的总和。Snuke 会以最佳方式来最大化自己的得分。

顺便说一下，作为 Snuke 的狂热粉丝，你计划做一些坏事来最大化得分。具体来说，在游戏开始之前，你将执行以下操作一次：

• 选择一个整数 $k$（$0 \\leq k \\leq N-1$），并将写在卡片上的整数按照向左循环移动 $k$ 个位置：卡片 $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$ 值时的得分。如果有多个值的 $k$ 可以使 $s$ 最大化，则任意输出其中一个即可。

示例输入 1

4
3 4 1 2

示例输出 1

1 7

如果你选择 $k=1$，卡片 $1,2,3,4$ 上的数字将变为 $4,1,2,3$。然后，游戏将按以下方式进行：

• Snuke 取走卡片 $1$。
• Mr. Min 取走卡片 $2$。
• Snuke 取走卡片 $4$。
• Mr. Min 取走卡片 $3$。

在这种情况下，Snuke 的得分为 $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