Background

Special for beginners, ^_^

Description

在马其顿王国的 ohide 湖里举行了一次潜水比赛。其中一个项目是从高山上跳下水，再潜水达到终点。这是一个团体项目，一支队伍由 n 人组成。在潜水时必须使用氧气瓶，但是每只队伍只有一个氧气瓶。最多两人同时使用一个氧气瓶 ，但此时两人必须同步游泳，因此两人达到终点的时间等于较慢的一个人单独游到 终点所需要的时间。好在大家都很友好，因此任何两个人后都愿意一起游水。安排一种潜水的策略，使得最后一名选手尽量早的到达终点。

Format

Input

第一行：队伍的人数 n（<=1000）。 以下 n 行，每行一个数，代表第 i 个人的游到终点的时间。

Output

最早到达终点的时间

Samples

3
1
3
4

8

Limitation

1s, 1024KiB for each test case.