题目描述

有 $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

输入

4
3 4 1 2

输出

1 7

样例 2

输入

2
1 1

输出

0 1

样例 3

输入

10
716893678 779607519 555600775 393111963 950925400 636571379 912411962 44228139 15366410 2063694

输出

7 3996409938

说明/提示

样例 1 解释

如果你选择 $k=1$，卡牌 $1,2,3,4$ 上将分别写有 $4,1,2,3$。游戏进行过程如下。

• Snuke 拿走卡牌 $1$。
• Min 先生拿走卡牌 $2$。
• Snuke 拿走卡牌 $4$。
• Min 先生拿走卡牌 $3$。

此情况下，Snuke 的得分为 $7$。

对于此输入，$k=2,3$ 同样为正确答案。