Maximizing the Array Sum via MEX Operations

You are given a sequence of n integers a₁, a₂, …, aₙ.

You are allowed to perform the following operation arbitrarily many times:

Choose an ordered pair of distinct indices (i, j) (that is, 1 ≤ i, j ≤ n and i ≠ j). Let

[ x = \max{a_i, a_j}\quad\text{and}\quad y = \operatorname{mex}{a_i, a_j}, ]

and then update

[ a_i = x,\quad a_j = y. ]

Recall that for a set S of nonnegative integers, \( \operatorname{mex}(S) \) is the smallest nonnegative integer not in S. In particular, note that when S has two elements:

• If S = \{0, 1\}, then \( \operatorname{mex}(S)=2 \).
• If one of the numbers is 0 and the other is not 1, then \( \operatorname{mex}(S)=1 \) (since 0 is present and 1 is missing).
• If the pair does not contain 0 then \( \operatorname{mex}(S)=0 \).

Your task is to maximize the sum \(\sum_{i=1}^n a_i\) after performing a sequence of operations (possibly zero operations).

Observation: An operation only increases the total sum when one of the numbers is 0. In fact, if we write the two numbers as \(a\) and \(b\) with \(a\le b\), then the operation changes the pair from \((a, b)\) to \((b, \operatorname{mex}\{a,b\})\). The increase is \(\operatorname{mex}\{a,b\} - a\), which is positive only when \(a=0\). Thus, the only way to boost the total sum is to use an operation on a pair where one element is 0. Moreover, if the other element is 1, the gain is 2 (since \(\operatorname{mex}\{0,1\}=2\)), and if it is not 1 the gain is only 1 (because \(\operatorname{mex}\{0,v\}=1\) for any \(v\neq1\)).

An optimal strategy is as follows:

1. Let s be the initial sum of the array, c₀ be the count of zeros, and c₁ be the count of ones in the initial array.
2. If there is no 0 then no operation increases the sum and the answer is simply s.
3. If there is at least one 0 then it is beneficial to use these 0's in operations. Using a 0 together with a 1 gives a gain of 2 while using a 0 with any other number gives a gain of 1. However, you are allowed to “recycle” a 1 so that it can participate repeatedly in operations provided you choose the order of indices wisely. In particular, you can fix one index with value 1 as a permanent partner in the operations. (When using the permanent partner, always put it in the i position so that its value remains 1 while the 0 from the other index (in the j position) gets updated.)
4. Thus, an optimal bonus that can be added to s is determined as follows:
   • If c₀ > 0 and there is already at least one 1 (i.e. c₁ > 0), then every 0 can be paired with the permanent 1 for a gain of 2, so the bonus is 2*c₀.
   • If there is no 1 initially (c₁ = 0), then you must first perform one conversion operation using two 0's to produce a 1. (Note that when applying the operation on two 0's, you can choose the assignment so that one of them remains 0 and the other becomes 1.) Then, every remaining 0 can be paired with that permanent 1 for a gain of 2. In this case the bonus is 2*(c₀ - 1) + 1. (The extra +1 comes from the initial conversion operation.)

Therefore, the answer is computed as follows:

[ \text{answer} = \begin{cases} s, & \text{if } c₀ = 0;\[1mm] s + 2\cdot c₀, & \text{if } c₀ > 0 \text{ and } c₁ > 0;\[1mm] s + 2\cdot (c₀ - 1) + 1, & \text{if } c₀ > 0 \text{ and } c₁ = 0. \end{cases} ]

Implement this logic.

inputFormat

The first line contains a positive integer n (n ≥ 1), the length of the sequence.

The second line contains n space‐separated integers representing the array a.

outputFormat

Output a single integer, the maximum possible sum \(\sum_{i=1}^n a_i\) after performing the operations optimally.

sample

2
0 2

3

</p>