你将按顺序遭遇 n 只宝可梦，第 i 只宝可梦的强度为 a_i。

对每只宝可梦，你可以选择将其放走或击败，收益规则如下：

放走宝可梦：获得 0 点经验值。

击败强度为 x 的宝可梦：基础获得 x 点经验值；若本次是你第偶数次击败宝可梦（第 2 次、第 4 次……），将额外获得 x 点经验值。

请计算你能获得的最大总经验值。

输入格式

第一行一个正整数 n，表示宝可梦的总数量。

第二行 n 个正整数 a_1, a_2, …, a_n，依次表示每只宝可梦的强度。

输出格式

输出一个整数，表示可获得的最大总经验值。

输入样例

5
1 5 3 2 7

输出样例

28

说明提示

1 ≤ n ≤ 2×10^5

1 ≤ a_i ≤ 10^9

限制

时间限制：1000ms，内存限制：256MiB