#P2217. 挑战积分

挑战积分

本题需要文件读写

文件 IO 为:输入文件 bonus.in,输出文件 bonus.out。请使用上述文件名读入和输出。

问题描述

市科技节设置了一条由 nn 个挑战站组成的体验路线。小航将依次经过这些挑战站,第 ii 个挑战站的基础积分为 aia_i。

每经过一个挑战站,小航可以选择完成该站的任务,也可以选择跳过。每个站只能选择一次,经过之后不能返回。

  • 如果跳过,获得 00 分,也不计入已完成任务的次数。
  • 如果完成,获得该站的基础积分。若这是小航第偶数次完成任务,还会额外获得一份该站的基础积分。

也就是说,第 1,3,5,…1,3,5,\ldots 次完成任务获得一份基础积分,第 2,4,6,…2,4,6,\ldots 次完成任务获得两份基础积分。这里的次数按实际完成的任务计算,与挑战站本身的编号无关。

请你求出小航最多可以获得多少积分。

输入格式

第一行包含一个正整数 nn,表示挑战站的数量。

第二行包含 nn 个正整数 a1,a2,…,ana_1,a_2,\ldots,a_n,表示各站的基础积分。

输出格式

输出一行一个整数,表示最多可以获得的积分。

样例输入 1

5
1 5 3 2 7

样例输出 1

28

样例输入 2

2
1000000000 1000000000

样例输出 2

3000000000

说明

公开分档大样例:下载 samples.zip。

评测数据规模

对于 100%100\% 的数据,保证 1≤n≤2×1051\le n\le2\times10^5,1≤ai≤1091\le a_i\le10^9,所有输入均为整数。

各测试点的附加限制如下表所示:

测试点编号 n≤n\le ai≤a_i\le 特殊性质
1∼41\sim4 2020 10910^9 无
5∼85\sim8 20002000
9∼109\sim10 2×1052\times10^5 A
11∼1211\sim12 B
13∼2013\sim20 无
  • 特殊性质 A:a1=a2=⋯=ana_1=a_2=\cdots=a_n。
  • 特殊性质 B:a1≥a2≥⋯≥ana_1\ge a_2\ge\cdots\ge a_n。

本题共 2020 个独立测试点,每点 55 分。