问题描述

有一组正整数，总数不超过 $1000$ ，其中最大值记为 $M$ 。 现要将它们划分成 $N$ 个集合，使得每个集合的元素之和与 $M$ 的差的绝对值的和最小。 集合 $A$ 中当前各元素之和记为 $SUM(A)$ ，称为 $A$ 的负荷；$SUM(A)$ 与 $M$ 之差的绝对值称为A的负荷与理想负荷的偏差，简称为A的偏差。 把这些整数划分成 $N$ 个集合的方法是：按照从大到小的顺序，依次为每个整数分别选择一个集合； 确定一个整数所属集合时，先计算各集合的负荷，将该整数分配给负荷最小的那个集合。 求使得各集合的偏差之和最小的划分方案中，集合的数目 $N$ 。如果这样的方案不止一种，则输出各方案中，集合数最大的那种方案的集合数 $N$ 。

输入格式

共输入 $K+1$ 个整数。其中第一个整数是 $K$ 代表要划分的整数总数，后面依次是 $K$ 个整数的值。 $K$ 不超过 $1000$ 。

输出格式

一个整数，代表集合数 $N$ 。

样例

输入

8
2 4 9 12 16 80 28 72

输出

3