← 返回题目列表

AtCoder · awc0010_b

B. 钢琴练习

中文机器翻译题面 查看原题

分数: 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