想象一下您有一个双胞胎兄弟或姐妹。拥有另一个与你长得一模一样的人似乎很不寻常。很难说拥有另一个自我是好还是坏。如果你确实有一个双胞胎,那么你很清楚那是什么感觉。
现在让我们想象一下您家中一个典型的早晨。你还没起床,妈妈就已经去上班了。她太匆忙了,差点忘了给两个心爱的孩子留下一些钱,让他们在学校食堂买午餐。她在钱包里摸索,发现了一些硬币,或者准确地说,是 n 个任意值 a1, a2, ..., an 的硬币。但由于妈妈时间不多了,所以她没有给你们两个分硬币。于是她潦草地写了一张纸条,要求你平分这笔钱。
当你醒来时,你发现了妈妈的硬币并读了她的纸条。 “但是为什么要平分钱呢?” ——你想。毕竟,你的双胞胎正在睡觉,他不会知道任何事情。所以你决定这样做:为自己挑选一些硬币子集,这样你的硬币的价值总和就严格大于你的双胞胎将拥有的剩余硬币的价值总和。然而,你正确地认为,如果你拿了太多硬币,双胞胎就会怀疑你受骗了。因此,你决定坚持以下策略以避免怀疑:你拿走最少数量的硬币,其价值之和严格大于剩余硬币的价值之和。在此基础上,确定按照所描述的方式划分所需的最少硬币数量。
输入
第一行包含整数 n (1 ≤ n ≤ 100) — 硬币数量。第二行包含 n 个整数 a1, a2, ..., an (1 ≤ ai ≤ 100) 的序列 — 硬币的值。所有数字均以空格分隔。
输出
在单行中打印单个数字 - 所需的最小硬币数量。
示例
输入 #1
2 3 3
输出 #1
2
输入 #2
3 2 1 2
输出 #2
2
注意
在第一个样本中,您必须拿走 2 个硬币(您和您的双胞胎的总和分别等于 6, 0)。如果您拿 1 个硬币,您将得到 3、3 的总和。如果您拿 0 个硬币,您将得到 0、6 的总和。这些变体不能满足您,因为您的总和应该严格大于双胞胎的总和。
在第二个示例中,一枚硬币对我们来说也不够。您可以选择值为 1、2 或 2、2 的硬币。在任何情况下,硬币的最小数量等于 2。