Hezardastan's Annual Report

Interview

Time limit1sMemory limit2048 MB

Summary

Given the page count of each chapter, find the fewest A4 sheets needed when every chapter starts on an odd page and no sheet mixes two chapters.

Level: Easy2 of 10
Topics: Math, Implementation
Solved: No attempts yet

Statement

Hezardastan is a major Iranian IT holding group that operates several innovative companies, including Cafebazaar, Divar, and Balad. The holding's annual report has $n$ chapters, and each chapter covers one company in the group. The chapters differ in length, so each one takes a different number of pages.

The report will be compiled into a single PDF and printed double-sided on A4 sheets. For aesthetic reasons, pages from two different chapters must not share a sheet. Each chapter must start on a fresh odd-numbered page, so after every chapter with an odd number of pages, one blank page is inserted. Find the minimum number of A4 sheets needed to print the entire report.

Input

The first line contains an integer $n$ ( $1 \le n \le 100$ ), the number of chapters. The second line contains $n$ space-separated integers, the number of pages in each chapter. All numbers in the input are positive integers at most $100$ .

Output

Print a single line containing the total number of A4 sheets needed to print the entire annual report.

Examples2

Example 1
Input
```
5
1 1 2 1 2
```
Expected output
```
5
```
Example 2
Input
```
8
1 2 3 2 2 5 4 2
```
Expected output
```
12
```