Description

麻将是一种常见的棋牌类游戏

小J现在学习了一种简单型的麻将游戏，它的规则如下

1:可以组成AA类的牌

2:可以组成AB类的牌,当满足B的面值=A的面值+1

Format

Input

现在给你一个数字N，代表有N种牌,面值从1到N。

N<=10^5

然后再给出每种牌各有多少张,张数<=10^9

Output

问你最多可搭配出多少套牌出来。

Samples

4
4
0
3
2

4

Hint

搭配成如下形式 (1,1),(1,1),(3,4),(3,4)