Phantasialand boasts of its famous theme park. The park is frequently visited. It is quite large park that some tourists visit it more than once to fully appreciate its offerings. One day, our Chefs decided to visit the park. There are total n Chefs, i-th of them wants to visit the park ti times.

Usually, the entry ticket for the park is very expensive. Today, being a weekend, park had an interesting offer for the visitors, "1x Zahlen, 2x Spaß" (pay once, visit twice), i.e. you can get a second free visit after the first paid visit. The procedure for visiting the park and availing the offer is as follows.

First time visitors should buy a ticket at the entrance of the park. Along with the ticket, you are offered an option of availing a voucher if you want a second visit.
Enter the theme park, enjoy your visit. While returning make sure to sign your name in the voucher. Any unsigned voucher will not allowed to take out of the park.
After the visit is done, the ticket counter takes back your ticket.
If it is your second time visit, then the counter will take back your voucher. No new voucher will be provided to you as you have already availed the offer.
You can avail the offer as many times as you wish in a day, i.e. offer is applicable for each visit with a paid ticket.

Obviously, this procedure has a flaw. The counter doesn't ask you to sign your name on the voucher at the time of providing it to make sure that the person buying the ticket is the one signing the voucher. So, if more than one Chefs enter the park, they can exchange their vouchers while they are inside the park.

Chefs thought of exploiting this flow. They wanted to buy minimum number of tickets. Can you help them in finding how many minimum tickets they should buy?

Let us take an example. There are two Chef's, Alice and Bob. Alice wants to visit the park three times and Bob only once. For their first visits, each of them buys a ticket and obtains their vouchers and visits the park. After they have entered their park, Bob gives his voucher to Alice. Alice signs her name on her own voucher and on the voucher given by Bob. In this way, she has two vouchers, which she can use to visit the park two more times. So, in total by buying two tickets, Alice can visit three times and Bob once.

Input
The first line of the input contains a single integer n denoting the number of Chefs.
The second line contains n space-separated integers t1, t2, ..., tn, where ti denotes the number of times i-th Chef wants to visit the park.

Output
Output a single integer corresponding to the minimum number of tickets Chefs needs to buy.

Constraints

1 ≤ n ≤ 10^5
1 ≤ ti ≤ 10^4

Example
Input 1:
2
3 1

Output:
2

Input 2:
4
1 2 3 3

Output:
5

Explanation
Example case 1. This example is already explained in the problem statement.

见题面

见题面