201382: [AtCoder]ARC138 C - Rotate and Play Game

Memory Limit：1024 MB Time Limit：2 S
Judge Style：Text Compare Creator：
Submit：0 Solved：0

Description

Score : $600$ points

Problem Statement

There are $N$ cards, indexed $1$ to $N$. Card $i$ has an integer $A_i$ written on it. Here, $N$ is even.

Snuke and Mr. Min will play a game. The game consists of $N$ turns, alternately taken by the two players, with Snuke going first. In each turn, the player does the following operation.

  • In Snuke's turn: He takes any card of his choice that is not taken by anyone yet.
  • In Mr. Min's turn: He takes the card with the minimum index that is not taken by anyone yet.

Snuke's score will be the sum of the integers written on the cards taken by Snuke. Snuke plays optimally to maximize the score.

Incidentally, being a big fan of Snuke, you are planning to do something nasty to maximize the score. Specifically, before the start of the game, you will do the following action once.

  • Choose an integer $k$ ($0 \leq k \leq N-1$) and cyclically shift the integers written on the cards by $k$ to the left: the cards $1,2,\cdots,N$ will have $A_{k+1},A_{k+2},\cdots,A_N,A_1,\cdots,A_k$ written on them.

Find the value $k$ that you should choose to maximize the score, and the resulting score when choosing that $k$.

Constraints

  • $2 \leq N \leq 2 \times 10^5$
  • $N$ is even.
  • $1 \leq A_i \leq 10^9$
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

$N$
$A_1$ $A_2$ $\cdots$ $A_N$

Output

Print the answer in the following format:

$k$ $s$

Here, $k$ is the integer you choose ($0 \leq k \leq N-1$), and $s$ is the score when choosing that $k$. If there are multiple values of $k$ that maximize $s$, printing any of them will be accepted.

Sample Input 1

4
3 4 1 2

Sample Output 1

1 7

If you choose $k=1$, the cards $1,2,3,4$ will have $4,1,2,3$ written on them. Then, the game will go as follows.

  • Snuke takes Card $1$.
  • Mr. Min takes Card $2$.
  • Snuke takes Card $4$.
  • Mr. Min takes Card $3$.

In this case, Snuke's score is $7$.

In this input, $k=2,3$ will also be accepted.

Sample Input 2

2
1 1

Sample Output 2

0 1

Sample Input 3

10
716893678 779607519 555600775 393111963 950925400 636571379 912411962 44228139 15366410 2063694

Sample Output 3

7 3996409938

Input

题意翻译

## 题面 A 与 B 在玩游戏，其中 A 先手。 有 $n$ 个数 $a_1-a_n$，A 每次可以任意取一个数，B 每次会取没有被取的数中下标最小的一数。 A 想最大化自己拿到的数字和。他可以选择一个数字 $k \in [0,n)$，把第 $1$ 至第 $k$ 个数依次提到数组的最后面，来实现他的目的。$k=0$ 时，相当于不做操作。 输入 $n$ 和 $a$ 数组，请输出 $k$，和 A 拿到的数字和。如果有多个 $k$，输出任一即可。 ## 数据范围 - $1 \leq n \leq 2 \cdot 10^5$ - $2 \mid n$ - $1\leq a_i \leq 10^9$ ## 样例解释 #1 选择 $k=1,2,3$ 均可，答案为 $7$。 以 $k=1$ 为例，数组将变为 $4,1,2,3$。之后执行以下过程： - A 取走 $4$ - B 取走 $1$ - A 取走 $3$ - B 取走 $2$ 注意这里说的是数值不是下标。

Source/Category

加入题单

算法标签：