← 返回题目列表

AtCoder · arc138_c

C. 旋转并玩游戏

中文机器翻译题面 查看原题

分数: 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