#agc053b. [agc053_b]Taking the middle

[agc053_b]Taking the middle

2N2N 张牌,编号为 12N1\sim 2N,第 ii 张牌价值 ViV_i。现在 Takahashi 和 Aoki 轮流取牌,每次 Takahashi 先取一张没有被取过的牌,之后 Aoki 取编号为剩余牌编号中位数的牌。重复以上步骤 NN 次,两人各取 NN 张牌。

请求出 Takahashi 取到的牌价值之和的最大值。

输入第一行一个整数 NN,第二行 NN 个整数 V1,V2,,VNV_1,V_2,\cdots,V_N

  • 1N2×1051\leqslant N\leqslant 2\times 10^5

  • 0Vi1090\leqslant V_i\leqslant 10^9

  • Vi V_i 均为整数。