该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目

有 $N$ 个敌人排成一排，第 $i$ 个敌人的血量为 $h_i$。当敌人的血量降至 0 或以下时，该敌人会被消灭。

游戏开始时，时间 $T$ 初始化为 0。从第 1 个敌人开始，你需要重复执行以下操作，直到所有敌人被消灭：

1. 将时间 $T$ 加 1；
2. 如果当前时间 $T$ 是 3 的倍数，当前敌人的血量减少 3；否则，当前敌人的血量减少 1。

当敌人的血量降至 0 或以下时，立即开始攻击下一个敌人。

求消灭所有敌人所需的时间 $T$。

输入

第一行包含一个整数 $N$（$1 \leq N \leq 2 \times 10^5$），表示敌人的数量。

第二行包含 $N$ 个整数 $h_1, h_2, \ldots, h_N$（$1 \leq h_i \leq 10^9$），表示每个敌人的初始血量。

输出

输出一个整数 $T$，表示消灭所有敌人所需的时间。

样例

3
6 2 2

8

9
1 12 123 1234 12345 123456 1234567 12345678 123456789

82304529

5
1000000000 1000000000 1000000000 1000000000 1000000000

3000000000

提示

• 对于样例 1：

  • 时间 $T=1$，攻击第 1 个敌人，血量从 6 减少到 5。
  • 时间 $T=2$，攻击第 1 个敌人，血量从 5 减少到 4。
  • 时间 $T=3$，攻击第 1 个敌人，血量从 4 减少到 1。
  • 时间 $T=4$，攻击第 1 个敌人，血量从 1 减少到 0，第 1 个敌人被消灭。
  • 时间 $T=5$，攻击第 2 个敌人，血量从 2 减少到 1。
  • 时间 $T=6$，攻击第 2 个敌人，血量从 1 减少到 -2，第 2 个敌人被消灭。
  • 时间 $T=7$，攻击第 3 个敌人，血量从 2 减少到 1。
  • 时间 $T=8$，攻击第 3 个敌人，血量从 1 减少到 0，第 3 个敌人被消灭。

• 对于样例 3，注意大整数运算可能导致溢出。