C - Triple Attack Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 300 点

問題文

あなたはゲームをプレイしています。

N 人の敵が一列に並んでおり、前から i 番目の敵の体力は H_i です。

あなたは 0 で初期化された変数 T を使い、全ての敵の体力が 0 以下になるまで次の行動を繰り返します。

  • 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

オーバーフローに注意してください。

Score : 300 points

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.