击鼓传花
内存限制: 256 Mb时间限制: 1000 ms
题目描述
小爱和小艾在玩一个游戏。游戏一共有 nn 轮，第 ii 轮有一个分数 a_ia
i
，在每一轮里，手上有花的人可以做出选择：
他可以选择保留花，这样，这一轮的分数就会送给对方；
他可以选择保留分数，这样，花就会送给对方；
游戏一开始，花在小爱手里，若假设双方均会使用最佳策略去得分，那么输出小爱的最后得分是多少？
输入格式
第一行：一个正整数 nn
第二行：nn 个正整数 a_ia
i
输出格式
单个正整数：表示小爱获得的分数
数据范围
对于 30%30% 的数据，保证 1\leq n\leq 501≤n≤50；
对于 60%60% 的数据，保证 1\leq n\leq 50001≤n≤5000；
对于 100%100% 的数据，保证 1\leq n\leq 200,0001≤n≤200,000；
1 \leq a_i \leq 100001≤a
i ≤10000；
样例数据
输入:
4
5 2 7 3
输出:
10
