1 or 2

AtCoder

IDarc121_d

Time2000ms

Memory256MB

Difficulty—

Snuke has a blackboard and $N$ candies. The _tastiness_ of the $i$\-th candy is $a_i$. He will repeat the operation below until he has no more candy. * Choose one or two of his candies and eat them (of course, they disappear). Then, write on the blackboard the total tastiness of the candies he has just chosen. Snuke wants to minimize $X-Y$, where $X$ and $Y$ are the largest and smallest values written on the blackboard, respectively. Find the minimum possible value of $X-Y$. ## Constraints * All values in input are integers. * $1 \leq N \leq 5000$ * $-10^{9} \leq a_i \leq 10^9$ ## Input Input is given from Standard Input in the following format: $N$ $a_{1}$ $a_{2}$ $\cdots$ $a_N$ [samples]

Samples

Input #1

3
1 2 4

Output #1

1

*   One optimal sequence of operations is to eat the candies with the tastinesses of $1$ and $2$ in the first operation, and then eat the candies with the tastiness of $4$ in the second operation.

Input #2

2
-100 -50

Output #2

0

*   It is optimal to eat both candies with the tastiness of $-100$ and $-50$ in the first operation.

Input #3

20
-18 31 -16 12 -44 -5 24 17 -37 -31 46 -24 -2 11 32 16 0 -39 35 38

Output #3

API Response (JSON)

{
  "problem": {
    "name": "1 or 2",
    "description": {
      "content": "Snuke has a blackboard and $N$ candies. The _tastiness_ of the $i$\\-th candy is $a_i$. He will repeat the operation below until he has no more candy. *   Choose one or two of his candies and eat them",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "arc121_d"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Snuke has a blackboard and $N$ candies. The _tastiness_ of the $i$\\-th candy is $a_i$.\nHe will repeat the operation below until he has no more candy.\n\n*   Choose one or two of his candies and eat them...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments