409674: GYM103677 K Wine Grapes

K. Wine Grapestime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

Carter owns a world-famous winery and realizes that demand for their wines has grown to such a point that they need to hire some help.

As their newest employee, they ask you to help them with the very secret recipe. The winery gets $$$n$$$ distinct types of grapes and to make a single bottle of wine, Carter uses one pound of $$$n - 1$$$ distinct grape types (so if $$$n = 4$$$, they will use $$$3$$$ different grapes, and one pound of each type to make the single bottle of wine). The big secret Carter lets you in on is that it doesn't actually matter which set of $$$n - 1$$$ grape types you pick, the blend will always turn out perfect so long as there are $$$n - 1$$$ different grape types used.

Carter has a big order of new grapes coming in so they want to clear up some inventory space. For grape type $$$i$$$, they would like to use at least $$$a_i$$$ pounds in making bottles of wine that day (since they have so much inventory, you can use as many pounds of $$$a_i$$$ you want, Carter just insists that you use at least $$$a_i$$$ pounds). Figure out the minimum number of bottles of wine you need to make so that for all grape types $$$i$$$, you have used at least $$$a_i$$$ pounds of it today.

Input

The first line of input contains a single integer $$$n$$$, representing the number of distinct grape types ($$$3 \leq n \leq 10^{5}$$$).

The second line of input contains $$$n$$$ space-separated integers where the $$$i$$$th integer represents $$$a_i$$$, the minimum number of pounds of grape $$$i$$$ you must use today ($$$1 \leq a_i \leq 10^{9}$$$).

Output

A single integer that represents the minimum number of bottles of wine you need to make in order to use at least $$$a_i$$$ pounds of grape $$$i$$$ for all $$$i$$$.

ExamplesInput

3
3 2 2

Output

4

Input

4
4 4 4 4

Output

6

Note

In example 1, we can make the following bottles (we need to use $$$2$$$ grape types in each bottle since $$$n = 3$$$ and in each bottle, we use one pound of each type listed):

1. Grape Type 1 and Grape Type 2
2. Grape Type 1 and Grape Type 3
3. Grape Type 1 and Grape Type 2
4. Grape Type 1 and Grape Type 3

Note that we ended up using $$$4$$$ pounds of grape type 1 but that is fine since we used at least $$$3$$$ as asked for and any attempt to do the same task in $$$3$$$ or fewer bottles will result in one of the grapes not being used enough times.