题目描述
小爱和小艾在玩一个游戏。游戏一共有 $n$ 轮，第 $i$ 轮有一个分数 $a_i$，在每一轮里，手上有花的人可以做出选择：
- 他可以选择保留花，这样，这一轮的分数就会送给对方；
- 他可以选择保留分数，这样，花就会送给对方；
游戏一开始，花在小爱手里，若假设双方均会使用最佳策略去得分，那么输出小爱的最后得分是多少？
输入
第一行：一个正整数 $n$
第二行：$n$ 个正整数 $a_i$
输出
单个正整数：表示小爱获得的分数
样例输入输出
提示
+ 对于 $30\%$ 的数据，保证 $1\leq n\leq 50$；
+ 对于 $60\%$ 的数据，保证 $1\leq n\leq 5000$；
+ 对于 $100\%$ 的数据，保证 $1\leq n\leq 200,000$；
+ $1 \leq a_i \leq 10000$；