问题描述

你在玩游戏。

有 $N$ 个敌人排成一行，从前面数第 $i$ 个敌人的生命值是 $H_i$。

一开始，变量 $T$ 的值为 0。你将重复以下动作，直到所有敌人的生命值变为 0 或更少。

• $T$ 增加 1。然后，攻击最靠前的生命值至少为 1 的敌人。如果 $T$ 是 3 的倍数，则敌人的生命值减少 3；否则，敌人的生命值将减少 1。

当所有敌人的生命值变为 0 或更少时，$T$ 的值是多少？

数据规模

$1≤N≤2×10^5$

$1≤H_i≤10^9$

所有输入值都是整数。

输入

输入来自标准输入，格式如下:

$N$

$H_1\ H_2\ \ldots\ H_N$

输出

打印答案。

3
6 2 2

8

这些操作按如下方式执行:

• $T$ 变为 1。攻击第 $1$ 个敌人，其生命值变为 $6-1=5$。
• $T$ 变为 2。攻击第 $1$ 个敌人，其生命值变为 $5-1=4$。
• $T$ 变为 3。攻击第 $1$ 个敌人，其生命值变为 $4-3=1$。
• $T$ 变为 4。攻击第 $1$ 个敌人，其生命值变为 $1-1=0$。
• $T$ 变为 5。攻击第 $2$ 个敌人，其生命值变为 $2-1=1$。
• $T$ 变为 6。攻击第 $2$ 个敌人，其生命值变为 $1-3=-2$。
• $T$ 变为 7。攻击第 $3$ 个敌人，其生命值变为 $2-1=1$。
• $T$ 变为 8。攻击第 $3$ 个敌人，其生命值变为 $1-1=0$。

9
1 12 123 1234 12345 123456 1234567 12345678 123456789

82304529

5
1000000000 1000000000 1000000000 1000000000 1000000000

3000000000

注意整数溢出。