分数: 600 点
问题陈述
有 N 卡片,已索引 1 to N。 卡 上面写着 i 有一个整数 上面写着 A_i 。 在这里, N 是偶数。
Snuke和Min先生将玩一个游戏。 游戏由 N 回合,由两名玩家轮流进行,Snuke 首先进行。 在每一回合中,玩家都会执行以下操作。
- 在斯努克的回合中:他拿走他选择的任何尚未被任何人拿走的牌。
- 轮到敏先生了:他拿了最小的牌 索引 尚未被任何人采用。
Snuke 的分数将是 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.
- 敏先生拿卡 2.
- Snuke 拿牌 4.
- 敏先生拿卡 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