Harry The Potter

## 题目描述 假设有一个包含 $n$ 个元素的数组 $a$ ，现在需要把此数组的每个元素都变为 $0$ 。 可以进行的操作有： - 选定两个数 $i$ 和 $x$ ，然后把 $a_i$ 减去 $x$ 。（注意， $x$ 可以是负数） - 选定三个数 $i,j$ 和 $x$ ，然后把 $a_i$ 减去 $x$ ，把 $a_j$ 减去 $x+1$ 。 请输出最少的操作次数。 ## 输入格式 第一行一个正整数 $n$ ，代表数组大小。 第二行， $n$ 个正整数分别代表 $a_1,a_2,a_3,\dots,a_{n-1},a_n$。 （没错， $i,j,x$ 你自己定） ## 输出格式 一行一个正整数表示最少操作次数。 ## 说明/提示 对于$100\%$的数据，$-10^{15}\le a_i\le10^{15},1\le n\le 20$ ### 样例解释 **样例#1** 只能将第一种操作执行三次。 **样例#2** 第一步，令$i=2,j=1,x=4$，数组变成$\{0,-1,-2\}$； 第二步，令$i=3,j=2,x=-2$，数组变成$\{0,0,0\}$，操作完毕。 **样例#3** 不必执行任何操作。

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 $ .

3
1 10 100

3

3
5 3 -2

2

1
0

0

In 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.