Minimum Operations to Insert Target via MEX

A multiset is a set in which elements may appear more than once. For example, \(\{0,0,1,2,2,5,5,5,8\}\) is a multiset.

You are given a multiset \(S\) whose elements belong to \(\mathbb{N}\) and a target natural number \(n\) (guaranteed that \(n\notin S\)). The multiset \(S\) is given in compressed form as a list \(f_0, f_1, \dots, f_{n-1}\) where \(f_i\) denotes the number of occurrences of \(i\) in \(S\).

You are allowed to perform the following operation any number of times:

1. Choose a (possibly empty) subset \(T\subseteq S\) such that \(T\) does not contain duplicate elements. (That is, if an element appears several times in \(S\), you may choose at most one occurrence of it to be in \(T\).)
2. For every element in \(T\), delete exactly one occurrence from \(S\).
3. Compute \(\operatorname{mex}(T)\) and insert it into \(S\). Recall that for any set \(T\subseteq \mathbb{N}\), \(\operatorname{mex}(T)\) is defined as the smallest nonnegative integer that is not in \(T\); for example, \(\operatorname{mex}(\{0,2,5\})=1\) and \(\operatorname{mex}(\varnothing)=0\).

Your goal is to make \(n\) appear in \(S\) using as few operations as possible. Print the minimum number of operations required.

Note. The final operation that gets \(n\) into \(S\) may involve removing several elements (if needed) so that the \(\operatorname{mex}\) of the chosen subset is \(n\). In other words, a final operation may choose \(T\) to be exactly \(\{0, 1, \dots, n-1\}\) once all elements from \(0\) to \(n-1\) are available in \(S\).

inputFormat

The first line contains a single integer \(n\) \((1 \le n \le 10^5)\) representing the target number (and the size of the frequency array).

The second line contains \(n\) space‐separated nonnegative integers \(f_0, f_1, \dots, f_{n-1}\), where \(f_i\) denotes how many times \(i\) appears in the multiset \(S\). It is guaranteed that \(n\) does not appear in \(S\).

outputFormat

Output a single integer, the minimum number of operations required to have \(n\) appear in \(S\).

sample

1
0

2