放置多米诺骨牌

题目描述

给一个图表，图表是一个直方图，$n$列的高度分别为$a_1, a_2, \dots, a_n$$(a_1 \ge a_2 \ge a_3 .... \ge a_n)$，你有许多大小为$1 \times 2$的多米诺骨牌$($可以旋转$)$，不重叠最多可以放置多少个呢

输入格式

第一行一个数字 $n$。

接下来一行 $n$ 个整数 $a_1, a_2, \dots, a_n$。

输出格式

一个数，表示答案。

样例输入

5
3 2 2 2 1

样例输出

4

数据范围

所有数据保证 $1\leq n\leq 300000, 1 \leq a_i \leq 300000$。