103682: [Atcoder]ABC368 C - Triple Attack

Problem Statement

You are playing a game.

There are $N$ enemies lined up in a row, and the $i$-th enemy from the front has a health of $H_i$.

You will repeat the following action until the healths of all enemies become $0$ or less, using a variable $T$ initialized to $0$.

• Increase $T$ by $1$. Then, attack the frontmost enemy with health $1$ or more. If $T$ is a multiple of $3$, the enemy's health decreases by $3$; otherwise, it decreases by $1$.

Find the value of $T$ when the healths of all enemies become $0$ or less.

Constraints

• $1 \leq N \leq 2\times 10^5$
• $1 \leq H_i \leq 10^9$
• All input values are integers.

Input

The input is given from Standard Input in the following format:

$N$
$H_1$ $H_2$ $\ldots$ $H_N$

Output

Print the answer.

Sample Input 1

3
6 2 2

Sample Output 1

8

The actions are performed as follows:

• $T$ becomes $1$. Attack the 1st enemy, and its health becomes $6-1=5$.
• $T$ becomes $2$. Attack the 1st enemy, and its health becomes $5-1=4$.
• $T$ becomes $3$. Attack the 1st enemy, and its health becomes $4-3=1$.
• $T$ becomes $4$. Attack the 1st enemy, and its health becomes $1-1=0$.
• $T$ becomes $5$. Attack the 2nd enemy, and its health becomes $2-1=1$.
• $T$ becomes $6$. Attack the 2nd enemy, and its health becomes $1-3=-2$.
• $T$ becomes $7$. Attack the 3rd enemy, and its health becomes $2-1=1$.
• $T$ becomes $8$. Attack the 3rd enemy, and its health becomes $1-1=0$.

Sample Input 2

9
1 12 123 1234 12345 123456 1234567 12345678 123456789

Sample Output 2

82304529

Sample Input 3

5
1000000000 1000000000 1000000000 1000000000 1000000000

Sample Output 3

3000000000

Beware of integer overflow.

问题陈述

你在玩一个游戏。

有$N$个敌人排成一行，从前面数第$i$个敌人的血量为$H_i$。

你会重复以下操作，直到所有敌人的血量变为$0$或以下，使用一个初始化为$0$的变量$T$。

• 将$T$增加$1$。然后，攻击血量为$1$或以上的最前面的敌人。如果$T$是$3$的倍数，敌人的血量减少$3$；否则，减少$1$。

找出当所有敌人的血量变为$0$或以下时的$T$的值。

约束条件

• $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$。攻击第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$。

样本输入2

9
1 12 123 1234 12345 123456 1234567 12345678 123456789

样本输出2

82304529

样本输入3

5
1000000000 1000000000 1000000000 1000000000 1000000000

样本输出3

3000000000

注意整数溢出。