問題一覧 > 通常問題

No.1925 Evil Spirit Minajigen

レベル : / AI推定難易度 : 2200 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 7
作問者 : 37zigen / テスター : tassei903
お気に入りにしたユーザー ProblemId : 3447 / 自分の提出
問題文最終更新日: 2022-05-02 00:26:25
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original

Problem Statement

Chased by the evil spirit Minajigen, YUKI has strayed into the first dimension and is trying to defect to the zeroth dimension. However, only unicellular organisms can live in the zeroth dimension.

YUKI has cell walls at $x_1, x_2, \ldots, x_{N+1}$ (in ascending order). YUKI's cells are the minimal intervals containing two cell walls; there are $N$ of them: $[x_1, x_2], [x_2, x_3], \ldots, [x_N, x_{N+1}]$.

Until only one cell remains, YUKI and Minajigen take turns choosing one cell wall and destroying it. For example, two cells $[1, 2], [2, 3]$ become one cell $[1, 3]$ when cell wall $2$ is destroyed. YUKI moves first and Minajigen moves second. Minajigen wants to make the size of the final cell as small as possible, and YUKI wants to make the size of the final cell as large as possible. Find the size of the final cell when both players act optimally.

Input

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

The sequence $A$ defined by $A_i = x_{i+1}-x_i$ is given.

  • All inputs are integers
  • $1 \leq N \leq 10^5$
  • $1 \leq A_i \leq 10^9$

Output

Output the size of the final cell. Print a newline at the end.

Sample

Sample 1
Input
1
10
Output
10

There is only one cell from the beginning.

Sample 2
Input
2
1 10
Output
11

Sample 3
Input
3
1 10 100
Output
11

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。