哈利·波特与魂器数组

• 时间限制：5 秒
• 内存限制：512 MiB

题目描述

给定一个包含 $n$ 个整数的数组 $a$。当数组中所有元素都变成 $0$ 时，数组被摧毁。

每次可以执行下列一种操作：

1. 选择一个下标 $i$ 和任意整数 $x$，令 $a_i\leftarrow a_i-x$；
2. 选择两个不同下标 $i,j$ 和任意整数 $x$，令 $a_i\leftarrow a_i-x$，同时令 $a_j\leftarrow a_j-(x+1)$。

注意，$x$ 可以是负数。求摧毁数组所需的最少操作次数。

输入格式

第一行包含一个整数 $n$。

第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$。

输出格式

输出一个整数，表示最少操作次数。

样例输入 1

3
1 10 100

样例输出 1

3

样例输入 2

3
5 3 -2

样例输出 2

2

样例输入 3

1
0

样例输出 3

0

数据范围

对于全部数据，$1\le n\le20$，$-10^{15}\le a_i\le10^{15}$。

题目来源：Codeforces 1286F。