Background

English statement. You must submit your code at the Chinese version of the statement.

Little T does not know what communication is.

Is it to understand a string of strange symbols, and then put it into someone else’s brain?

Is it to obtain some abstract knowledge, and then use it to break one’s own habits?

In order to communicate, Little T finally decided to connect to a voltage of $\text{220V}$.

Problem Description

t1k1x1ww。

Little T stares at this string of symbols that he cannot understand, and decides to first communicate an OI problem with you.

Little T has a rooted tree. It has a total of $k$ leaf nodes, and he also tells you that the depths of these leaf nodes are $a_1\dots a_k$. Please help him compute the minimum number of nodes this tree can contain. Little T guarantees that there exists at least one such tree.

If you are not familiar with some definitions in the statement, we are happy to remind you:

• A simple path in a graph is a path that does not repeat vertices and does not repeat edges.
• A tree is a connected graph in which there is exactly one simple path between any two vertices. In a tree, we choose one node as the root.
• A leaf node in a tree is a node that is not the root and 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.

Input Format

The first line contains an integer $k$.

The next line contains $k$ integers, describing $a_1\dots a_k$.

Output Format

Output a single integer on one line, representing the answer.

4
2 3 4 5

8

7
6 6 7 8 4 2 4

14

Hint

Sample Explanation

• For the first group of testdata, the following is one possible tree:

Its size is $8$. The depths of leaves $3, 5, 6, 8$ are $2, 3, 4, 5$, respectively. It is easy to prove that no tree of size $\leq 7$ satisfies the requirements.

Constraints and Notes

This problem uses bundled tests and subtask dependencies.

• Subtask 0 (0 pts): samples.
• Subtask 1 (30 pts): $k = 2$.
• Subtask 2 (30 pts): $a_1 = a_2 = \dots = a_k$.
• Subtask 3 (40 pts): no special restrictions. Depends on subtasks $0 \sim 2$.

For all data, it is guaranteed that $1 \leq k \leq 10^5$, $2 \leq a_i \leq 10^5$, and there exists at least one such tree.

Translated by ChatGPT 5