Background

The score for this problem follows the original COCI setting, with a full score of $100$.

Problem Description

Mirko found $N$ chains in the attic. Each chain consists of several links, and each link has at most two neighboring links. Each link can be opened or closed, so a chain can be split apart or connected into a longer chain.

Mirko wants to connect all chains into one huge chain, while opening and closing as few links as possible.

For example, suppose Mirko has only $3$ chains, and each chain has only one link. He can open one of them, connect the other two to it, and then close it.

Given the number of chains and the length of each chain, find the minimum number of links that Mirko must open and close so that they all become one long chain.

Input Format

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

The second line contains $N$ positive integers $L_i\ (1\le L_i\le 10^6)$, where $L_i$ is 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.

2
3 3

1

3
1 1 1

1

5
4 3 5 7 9

3

Hint

Translated by ChatGPT 5