F. Harry The Pottertime limit per test9 secondsmemory limit per test1024 megabytesinputstandard inputoutputstandard outputTo 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 if all its elements are zeroes. To destroy the array, Harry can perform two types of operations:  choose an index i (1 \le i \le n), an integer x, and subtract x from a_i. 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.InputThe 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}).OutputOutput a single integer — the minimum number of operations required to destroy the array a.ExamplesInput
3
1 10 100
Output
3
Input
3
5 3 -2
Output
2
Input
1
0
Output
0
NoteIn the first example one can just apply the operation of the first kind three times.In the second example, one can apply the operation of the second kind two times: first, choose i = 2, j = 1, x = 4, it transforms the array into (0, -1, -2), and then choose i = 3, j = 2, x = -2 to destroy the array.In the third example, there is nothing to be done, since the array is already destroyed.
3
1 10 100

3 
['brute force', 'constructive algorithms', 'dp', 'fft', 'implementation', 'math', '*3100']