T2 基层干部

题目信息

时间限制: 1s

空间限制: 512M

输入文件: girl.in

输出文件: girl.out

题目描述

B 市需要把新上任的 $n$ 位基层干部分配到下属的两个县城，均衡度是分配干部的首要指标，当第 $i$ 位干部和第 $\lfloor \frac i2\rfloor$ 位干部被分配到同一个县城时，会产生 $d_i$ 的均衡度。由于干部之间的私人关系错综复杂，所以并不保证每个 $d_i$ 都是正整数，那么均衡度最大的方案是什么呢？分配到下属两个县城干部数量需要相同

输入格式

第一行输入一个正整数 $n$，表示新上任的干部数量

第二行输入 $n$ 个空格分开的整数 $d_i$，含义如题所示

输出格式

一行一个正整数，表示最优策略下能得到的最大均衡度。

样例

样例输入 1

6
14 10 -7 -50 -50 20

样例输出 1

20

数据范围与提示

对于所有的测试点，满足 $n$ 为偶数，$n \leq 450,-10^9 \leq d_i \leq 10^9$

• 对于 $10 \%$ 的数据，满足 $n \leq 3$
• 对于 $30 \%$ 的数据，满足 $n \leq 20$
• 对于 $80 \%$ 的数据，满足 $n \leq 80$