Connecting Chains

Mirko has discovered N chains in the attic. Each chain is composed of a number of links, and every link (or knot) is connected to at most two other links. Each link can be opened or closed. By opening a link, it can be removed from its chain and later be used as a connector to join two chains together when it is closed again.

Mirko wishes to join all the chains together to form one long chain while modifying (i.e. opening or closing) as few links as possible. Note that when a link is opened it requires one operation, and when it is closed it requires another operation, so using a link as a connector costs 2 operations in total.

There is a useful observation. Suppose a chain consists of exactly one link. If we choose to completely sacrifice that chain (i.e. open its only link), then the single opened link (with two free ends) can be used to join two other chains together. In this case the sacrifice not only provides a connector but also completely removes one chain from the list. In contrast, if we open an end link from a chain that has at least two links, the chain remains as a component (although one link is removed) and that operation can only contribute one connection between two chains.

Thus, if we let T = N be the total number of chains and let A be the number of chains that have exactly one link, then:

• If T = 1, no operation is needed.
• If T > 1, we need to merge the T chains into one chain. Merging two chains requires a connector (which costs 2 operations). When a chain of length 1 is sacrificed, it effectively reduces the number of chains by 2 (one because that chain is removed and one merge is achieved by using its open link to connect two other chains). On the other hand, opening one end link from a longer chain only helps merge two chains by 1.

Overall, if we let x be the number of one‐link chains that we sacrifice (each saving one extra merge) and T-1 be the number of merges needed, then we must have:

[ 2x + y = T-1 \quad (\text{with } y \text{ being the number of merges done using normal operations}) ]

The total cost in operations is 2 for each merge whether it is done by sacrificing a one‐link chain or using a normal end‐link operation. When a sacrifice is applied, it counts 2 operations but yields a benefit of 2 merges instead of 1. To minimize the total operation cost, we want to maximize the number of sacrifices. However, we can only sacrifice up to A chains, and we cannot use sacrifice when there are only 2 chains (because sacrificing in that case would overshoot the merge count).

Therefore, one optimal strategy is to sacrifice x = min(A, \lfloor( T-1)/2\rfloor) chains among those with one link. Then, the remaining merges are done via normal operations. The minimum total number of operations required is:

[ \text{Cost} = 2\times((T-1) - x)\text{.} ]

Given that T = N, the answer is computed as follows:

[ \text{Answer} = 2\times( N-1 - \min\Bigl(A, \left\lfloor\frac{N-1}{2}\right\rfloor\Bigr) ) ]

</p>

inputFormat

The first line contains a single integer N (the number of chains). The second line contains N positive integers, where the i-th integer L_i represents the number of links in the i-th chain.

Note: It is guaranteed that each chain has at least 1 link.

outputFormat

Output a single integer – the minimum number of link operations (openings and closings, each counting as 1 operation) needed to connect all chains into one long chain.

sample

3
1 1 1

2

</p>