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

N/A

N/A

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.