题目描述

$Polycarp$有一个有$n$个数的数组，他会轮流从中删去数，比如：奇数-偶数-奇数-偶数-奇数-偶数-奇数-偶数···$\ \ \$或：偶数-奇数-偶数-奇数-偶数-奇数-偶数-奇数···直到无法删除。

输入格式

第一行:一个数字$n( 1 \le n \le 2000 1≤n≤2000 )$表示数组大小。

第二行：$n$个数，表示$a_{1},a_{2},a_{3}...a_{n} (0\le a_{i} \le 10^{6})$中的数。

输出格式

一个数，表示数组中剩余数的最小和。

若整个数组可以删除，输出$0$

样例

5
1 5 7 8 2

0

6
5 1 2 4 6 3

0

2
1000000 1000000

1000000