Placing Dominoes

Problem Description

You are given a histogram-like figure with $n$ columns whose heights are $a_1, a_2, \dots, a_n$ ($a_1 \ge a_2 \ge a_3 \dots \ge a_n$). You have many $1 \times 2$ dominoes (which may be rotated). What is the maximum number of dominoes you can place without overlap?

Input Format

The first line contains an integer $n$.

The next line contains $n$ integers $a_1, a_2, \dots, a_n$.

Output Format

Output one number: the answer.

Sample Input

5
3 2 2 2 1

Sample Output

4

Constraints

All data guarantee $1 \le n \le 300000$, $1 \le a_i \le 300000$.