A13255 | Harry The Potter

To defeat Lord Voldemort, Harry needs to destroy all horcruxes first. The last horcrux is an array $a$ of $n$ integers, which also needs to be destroyed. The array is considered destroyed is all its elements are zeroes. To destroy the array, Harry can perform two types of operations:

1. choose an index $i$ ( $1 \le i \le n$ ), an integer $x$ , and subtract $x$ from $a_i$ .
2. choose two indices $i$ and $j$ ( $1 \le i, j \le n; i \ne j$ ), an integer $x$ , and subtract $x$ from $a_i$ and $x + 1$ from $a_j$ .

Note that $x$ does not have to be positive.

Harry is in a hurry, please help him to find the minimum number of operations required to destroy the array and exterminate Lord Voldemort.

The first line contains a single integer $n$ — the size of the array $a$ ( $1 \le n \le 20$ ).

The following line contains $n$ integers $a_1, a_2, \ldots, a_n$ — array elements ( $-10^{15} \le a_i \le 10^{15}$ ).

Output a single integer — the minimum number of operations required to destroy the array $a$ .