分数: 233 分
问题陈述
高桥立志成为一名钢琴家,今天他决定演奏 N 练习曲目按顺序从 1-st 到 N-th。
的 树的 i- 第一块的难度为整数 D_i。演奏每首曲子所需的时间由以下规则决定:
- 的 树的 1-st 件需要 D_1 执行分钟。
- 对于 2- 第 5 块开始(2 \leq i \leq N),演奏时间取决于当前曲目与前一首曲目难度之间的关系。
- 如果难度是 严格大于 比上一篇(D_{i-1} < D_i),那么上一首作为热身,所以时间减少到 \lfloor D_i / 2 \rfloor 分钟。在这里, \lfloor x \rfloor 表示不超过的最大整数 x (即除以得到的值 D_i by 2 并向下舍入)。
- 如果难度小于或等于前一首(D_{i-1} \geq D_i),不应用任何减少,并且该作品需要 D_i 分钟。
当高桥按照从 1-st 到 N-th,总共需要多少分钟?
约束
- 1 \leq N \leq 2 \times 10^5
- 1 \leq D_i \leq 10^9
- 所有输入均为整数。
输入
N D_1 D_2 \ldots D_N
- 第一行包含一个整数 N 代表件数。
- 第二行包含 N 整数 D_1, D_2, \ldots, D_N 以空格分隔,代表每件作品的难度。
输出
在一行中打印高桥表演所有曲目所需的总时间(以分钟为单位)。
示例输入 1
5 3 5 4 8 10
示例输出 1
18
示例输入 2
7 1 2 3 4 5 6 7
示例输出 2
13
示例输入 3
10 100 50 200 200 300 150 400 500 600 100
示例输出 3
1600