Patrick is playing Boomerang Fu on the Nintendo Switch. Unfortunately, everyone else plays the game all the time. They know every trick, never miss, and have been putting Patrick in his place.

To give Patrick a chance, the group creates a special game mode with ~N~ opponents. Opponent ~i~ is defeated after Patrick hits them ~A_i~ times.

Each boomerang throw can do the following:

• Hit one opponent on the way out.
• Hit one opponent on the way back.

The two hits from a single throw must target different opponents. Patrick may also use only one of the two hits. Each hit reduces the chosen opponent's remaining required hits by ~1~.

Assume Patrick can choose his targets perfectly. Find the minimum number of boomerang throws needed to defeat every opponent.

Input

The first line contains an integer ~N~ (~1 \leq N \leq 2\times10^5~), the number of opponents.

The second line contains ~N~ integers ~A_1,A_2,\dots,A_N~ (~1 \leq A_i \leq 10^9~), where ~A_i~ is the number of times Patrick must hit opponent ~i~.

Output

Output a single integer: the minimum number of boomerang throws needed to defeat every opponent.

Examples

Input 1

4
2 1 1 2

Output 1

3

Patrick can use the throws as follows:

1. Hit opponents ~1~ and ~4~.
2. Hit opponents ~1~ and ~2~.
3. Hit opponents ~3~ and ~4~.

This delivers all ~6~ required hits in ~3~ throws.

Input 2

3
5 1 2

Output 2

5

Opponent ~1~ needs ~5~ hits, but Patrick cannot hit the same opponent twice with one throw. Therefore, at least ~5~ throws are required. Patrick can achieve this by pairing three of those hits with the hits needed for the other opponents.