Description

Charming 正在和 $n$ 只大怪兽战斗，每只怪兽都有一个生命值 $hp_i$，当怪物的生命值小于等于 $0$ 时，则视为该怪物已被消灭。

Charming 有两把武器，一把名为阿姆斯特朗回旋加速喷气式阿姆斯特朗炮，每秒可指定一只怪兽使其生命值降低 $1$；另一把名为宇宙最强之刃万物终结无尽星空，每秒可指定一只怪兽使其生命值降低 $2$。

每秒两把武器可以攻击同一只怪兽，也可以攻击两个不同的怪兽。

已知第 $i$ 只怪兽的血量为 $hp_i$。Charming 很饿，想早点干饭，所以他想知道最快要多久才能打完收工。请你帮忙算一算 Charming 至少要多少时间才能消灭完所有怪兽。

Input

输入的第一行为一个整数 $n$ ($1 \leq n \leq 10^5$)。

第二行共有 $n$ 个数，第 $i$ 个数 $hp_i$ ($1 \leq hp_i \leq 10^4$) 表示第 $i$ 个怪物的初始血量。

Output

输出一个整数，表示消灭完所有怪兽的最小用时。

Samples

1
1

1

3
2 2 1

2

4
1 2 1 1

2

Resources

电子科技大学第十三届 ACM 趣味程序设计竞赛