给定一个长度为 $n$ 的序列 $a_1, a_2, \dots, a_n$。

你需要执行以下操作若干次（可以是零次）： 选择一个下标 $i$（$1 \le i < n$），使得 $a_i > 0$ 且 $a_{i+1} > 0$。然后，将 $a_i$ 减 $1$，并将 $a_{i+1}$ 减 $1$。

你的目标是最大化序列中非零元素的个数。请输出这个最大值。

输入格式

第一行包含一个整数 $n$（$1 \le n \le 2 \times 10^5$）。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$0 \le a_i \le 10^9$）。

输出格式

输出一个整数，表示操作后序列中非零元素的最大个数。

样例

输入格式 1

3
2 2 2

输出格式 1

3

说明

在样例 1 中，我们可以将 $a_1$ 和 $a_2$ 同时减 1，得到序列 $1, 1, 2$。此时所有元素均非零，个数为 3。

输入格式 2

4
1 0 1 0

输出格式 2

2

输入格式 3

6
0 1 1 1 1 0

输出格式 3

4

说明

在样例 3 中，我们可以将 $a_2$ 和 $a_3$ 减 1，将 $a_4$ 和 $a_5$ 减 1，得到 $0, 0, 0, 0, 0, 0$ 是错误的。更好的做法是：将 $a_2$ 和 $a_3$ 减 1 得到 $0, 0, 0, 1, 1, 0$，然后将 $a_4$ 和 $a_5$ 减 1 得到 $0, 0, 0, 0, 0, 0$。实际上，我们可以通过操作使得最终有 4 个非零元素，例如保持 $a_2, a_3, a_4, a_5$ 不变是不可能的，但我们可以通过合理的操作达到最优解。