Rong Kong is a ~~filial~~ boy. There are N pears on the table. Both he and his brother can eat them. They both want to eat as much as they can. Each of them weighs a[i]. It costs a[i] time for a boy to eat a pear weighing a[i] and it gives him a[i] satisfaction. He can't stop eating a pear once he started to do it.Kong Rong starts to eat at time 0 and his brother starts to eat at time 0.5. And obviously, no one can take the other's pear when he is eating it. If both Rong Kong and his brother eat optimally, tell Rong Kong how to get the most satisfaction.

Example:

4

1 2 3 4

Answer:

6

Explanation:

Rong Kong first eats the pear weighing 2, then his parents will say he is a filial boy:)

Subtask 1:n<=20

Subtask 2:n<=1e5, a[i] can all be written as 2^k, k is a non-negative integer.

Subtask 3:n<=1e5, a[i]=i holds.

Subtask 4:n<=100

subtask 5:n<=1e5

a[i]<=1e5 always holds.