Indifferent

AtCoder

IDrelay2_j

Time2000ms

Memory256MB

Difficulty—

We have $2N$ pots. The market price of the $i$\-th pot $(1 ≤ i ≤ 2N)$ is $p_i$ yen (the currency of Japan). Now, you and Lunlun the dachshund will alternately take one pot. You will go first, and we will continue until all the pots are taken by you or Lunlun. Since Lunlun does not know the market prices of the pots, she will always choose a pot randomly from the remaining pots with equal probability. You know this behavior of Lunlun, and the market prices of the pots. Let the sum of the market prices of the pots you take be $S$ yen. Your objective is to maximize the expected value of $S$. Find the expected value of $S$ when the optimal strategy is adopted. ## Constraints * $1 ≤ N ≤ 10^5$ * $1 ≤ p_i ≤ 2 × 10^5$ * All input values are integers. ## Input Input is given from Standard Input in the following format: $N$ $p_1$ $:$ $p_{2N}$ [samples]

Samples

Input #1

1
150000
108

Output #1

150000.0

Naturally, you should choose the $150000$ yen pot.

Input #2

Output #2

183333.3333333333

First, you will take one of the $100000$ yen pots. The other $100000$ yen pot will become yours if it is not taken in Lunlun's next turn, with probability $2/3$. If it is taken, you will have to settle for a $50000$ yen pot. Thus, the expected value of $S$ when the optimal strategy is adopted is $2/3 × (100000 + 100000) + 1/3 × (100000 + 50000) = 183333.3333…$

API Response (JSON)

{
  "problem": {
    "name": "Indifferent",
    "description": {
      "content": "We have $2N$ pots. The market price of the $i$\\-th pot $(1 ≤ i ≤ 2N)$ is $p_i$ yen (the currency of Japan). Now, you and Lunlun the dachshund will alternately take one pot. You will go first, and we w",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "relay2_j"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "We have $2N$ pots. The market price of the $i$\\-th pot $(1 ≤ i ≤ 2N)$ is $p_i$ yen (the currency of Japan).\nNow, you and Lunlun the dachshund will alternately take one pot. You will go first, and we w...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments