Sasha is playing a new game “Vanjurs Fate” and is now preparing for a battle with the final boss, Vanjur. Sasha has N heroes. Usually, he levels up all his heroes to the maximum and, before the battle with the boss, gathers them together so as not to leave the boss any chances. Right now, all of Sasha’s heroes are leveling up in N different locations, with exactly one hero in each location. Sasha distributed the heroes so that they could gain as much experience as possible, but now he has problems gathering all the heroes in the location with Vanjur. At the moment, none of the heroes is in the boss’s location.

Sasha knows that the i-th hero needs exactly d_i seconds to reach the boss’s location, Vanjur, on their own. Also, while leveling up the heroes, Sasha found a legendary book. Any hero can read it instantly, after which the book is destroyed. The hero who reads the book will permanently gain the mass teleportation skill. They will be able to teleport themselves and all heroes in the same location with them to any point in any other location in 1 second. This skill can be used any number of times.

Sasha wants to gather all the heroes in the boss’s location in the minimum possible time. He can order each hero without the skill either to reach the boss’s location on their own in d_i seconds, or to wait for the appearance of a hero with the teleportation skill and travel with them after that. For the hero with the mass teleportation skill, Sasha can choose any route through the locations; the only requirement is that they also end up in the boss’s location in the end. All heroes will start carrying out the orders simultaneously. Help Sasha and find the minimum time needed to gather all the heroes in Vanjur’s location.

The first line contains one integer N — the number of heroes (1 ≤ N ≤ 10⁵).

The second line contains N integers d_i — the time in seconds it takes for the i-th hero to reach the boss’s location on their own (1 ≤ d_i ≤ 10⁹).

Print one integer — the minimum time in which Sasha will gather all the heroes in the boss’s location.

In the first test case, Sasha can give the book to the second hero and tell them to teleport immediately to the boss. Then the first and second heroes will arrive at the boss in 1 second, and the third hero will arrive in 2 seconds.

In the second test case, the book can be given to the third hero and told to pick up the first, fourth, and sixth heroes. Then they will teleport together to the boss’s location in 4 seconds. The second and fifth heroes will reach the boss’s location on their own in 4 seconds, and the seventh hero will arrive in 1 second. That is, all heroes will arrive at Vanjur after 4 seconds.