Problem Description

Mirko found \( N \) chains in the attic. Each chain consists of several links, where each link can have at most two adjacent links. Each link can be opened or closed, allowing the chains to be separated or connected into longer chains.

Mirko wants to connect all the chains into one giant chain, with the minimum number of links opened or closed.

For example, if Mirko has only 3 chains, each with a single link, he can open one of them and connect the other two before closing it.

Given the number of chains and the length of each chain, find the minimum number of links Mirko must open and close to connect them all into one long chain.

Input Format

The first line contains an integer \( N \) \( (2 \le N \le 5 \times 10^5) \), representing the number of chains.

The second line contains \( N \) positive integers \( L_i \) \( (1 \le L_i \le 10^6) \), representing the length of the \( i \)-th chain.

Output Format

Output a single integer on one line, representing the minimum number of links that need to be opened.

Sample Input and Output

Sample Input #1

2
3 3

Sample Output #1

1

Sample Input #2

3
1 1 1

Sample Output #2

1

Sample Input #3

5
4 3 5 7 9

Sample Output #3

3

见题面 Input 部分

见题面 Output 部分