The current selected programming language is C$.$ We emphasize the submission of a fully working code over partially correct but efficient code. Once submitted, you cannot review this problem again. You can use printf$()$ to debug your code. The printf$()$ may not work in case of syntax$/$runtime error. The version of GCC being used is $5\mathrm{.}5\mathrm{.}0.$

A travelling salesperson works in N towns. Each day the salesperson sells products in one of the towns. The towns that are chosen on any two successive days should be different, and a town i can be chosen at most citimes.

Write an algorithm to determine the number of days when the salesperson can sell in the given towns following these rules.

Input

The first line of the input consists of an integer $-$ num, representing the number of towns$($N$).$

The next line consists of N space$-$separated integers $-$ countTown$0,$ countTown$1,......,$ countTownN$-1,$representing the number of times each town can be chosen.

Output

Print an integer representing the maximum number of days during which the salesman can work.

Constraints

$1<=$ num $<=5*104$

$1<=$ countTowni$<=$ num

$\backslash$Sigma countTowni$<=105$

$0<=$ i $<$ num

Example

Input:

$3$

$723$

Output:

$11$

Explanation:

The first, second and third towns are chosen $7,2$ and $3$ times respectively.

The different towns are selected on successive days in a sequence: first, second, first, third, first, second, first, third, first, third, first.

So the maximum number of days during which a salesman can sell is $11.$ HAVING THIS FUNCTION : int maxDaysToWork$($array$\_$single$\_$int countTown$)\{$ int answer; $//$ Write your code here return answer;$\}$ COMPLETE THIS FUNCTION