分数: 300 点
问题陈述
您正在玩游戏。
有 N 敌人排成一排,然后 i前方第一个敌人的生命值为 H_i.
你将重复以下动作,直到所有敌人的生命值变为 0 或更少,使用变量 T 初始化为 0.
- 增加 T by 1。然后,用生命值攻击最前面的敌人 1 或更多。如果 T 是的倍数 3,敌人的生命值减少 3;否则,它会减少 1.
查找值 T 当所有敌人的生命值变为 0 或更少。
约束
- 1 \leq N \leq 2\times 10^5
- 1 \leq H_i \leq 10^9
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N H_1 H_2 \ldots H_N
输出
打印答案。
示例输入 1
3 6 2 2
示例输出 1
8
执行的操作如下:
- T 变为 1。攻击第一个敌人,其生命值变为 6-1=5.
- T 变为 2。攻击第一个敌人,其生命值变为 5-1=4.
- T 变为 3。攻击第一个敌人,其生命值变为 4-3=1.
- T 变为 4。攻击第一个敌人,其生命值变为 1-1=0.
- T 变为 5。攻击第二个敌人,其生命值变为 2-1=1.
- T 变为 6。攻击第二个敌人,其生命值变为 1-3=-2.
- T 变为 7。攻击第三个敌人,其生命值变为 2-1=1.
- T 变为 8。攻击第三个敌人,其生命值变为 1-1=0.
示例输入 2
9 1 12 123 1234 12345 123456 1234567 12345678 123456789
示例输出 2
82304529
示例输入 3
5 1000000000 1000000000 1000000000 1000000000 1000000000
示例输出 3
3000000000
注意整数溢出。