Minimum Number of Nodes in a Rooted Tree

Little T has a rooted tree with exactly k leaf nodes. He also tells you that the depths of these leaf nodes are given as a₁, a₂, ..., a_k (where the depth of a node is defined as the number of nodes on the simple path from the root to that node). A node is considered a leaf if it is not the root and its degree is 1. It is guaranteed that at least one such tree exists.

Your task is to compute the minimum number of nodes that such a tree can have.

If you are not familiar with some of the definitions, here are some reminders:

• A simple path in a graph is a path that does not repeat vertices or edges.
• A tree is a connected graph in which any two vertices are connected by exactly one simple path. In a tree, one vertex is chosen as the root.
• A leaf node in a tree is a node (other than the root) that has degree 1.
• The depth of a node in a tree is the number of nodes on the simple path from that node to the root.

To achieve the minimum number of nodes, one optimal strategy is to share as many nodes as possible among the paths leading from the root to the leaves. In particular, if the minimum depth among the leaves is m = \(\min_{1 \le i \le k} a_i\), then you can share a common chain of length m - 1 for all leaves. Each leaf then extends with a branch of length a_i - (m - 1). Therefore, the minimum number of nodes in the tree is given by:

[ \text{ans} = \sum_{i=1}^{k} a_i - (k - 1) (m - 1). ]

inputFormat

The input consists of two lines.

• The first line contains one integer k (1 ≤ k ≤ 10⁵), representing the number of leaf nodes.
• The second line contains k space-separated integers a₁, a₂, ..., a_k (2 ≤ a_i ≤ 10⁹), where each a_i denotes the depth of a leaf node.

outputFormat

Output a single integer denoting the minimum number of nodes that the tree can have.

sample

2
2 3

4