[160A] Gemelos

Enlace a Codeforces

Imagina que tienes un hermano o hermana gemela. Tener a otra persona que se vea exactamente como tú parece muy inusual. Es difícil decir si tener un alter ego es algo bueno o malo. Si tienes un gemelo, entonces sabes bien como se siente.

Ahora imaginemos una mañana típica en tu familia. Aún no te has levantado, y tu Mamá ya se fue a trabajar. Ella estaba tan apurada que casi olvido dejar a sus dos queridos hijos algo de dinero para compar almuerzos en la cafetería de la escuela. Escudriño en el bolso y encontró unas cuantas monedas, o para ser exactos, $n$ monedas de valores arbitrarios $a_1,a_2, \ldots, a_n$. Pero como a Mamá no le quedaba mucho tiempo, no dividió las monedas para ustedes dos. Así que escribió una nota pidiéndosle dividir las monedas equitativamente.

Cuando despertaste, encontraste las monedas de Mamá y leíste su nota. "Pero, ¿Por qué dividir las monedas igualmente?" - pensaste. Después de todo, tu gemelo está durmiendo y no sabrá nada. Por lo que decidiste actuar de este modo: seleccionarías para ti mismo un subconjunto de las monedas de modo que la suma de los valores de tus monedas sea estrictamente mayor que la suma de los valores de las monedas restantes que tendrá tu gemelo. Sin embargo, pensaste correctamente que si tomabas demasiadas monedas, el gemelo sospechará el engaño. Por lo tanto, decidiste adherirte a la siguiente estrategia para evitar sospechas: tomas el número mínimo de monedas tal que su suma sea estrictamente mayor que la suma de las monedas restantes. Sobre esta base, determina qué número mínimo de monedas necesitas tomar para dividirlas de la manera descrita.

Entrada

La primera línea contiene un entero $n$ ($1 \leq n \leq 100$) - el número de monedas. La segunda línea contiene una secuencia de $n$ enteros $a_1,a_2,\ldots, a_n$ ($1 \leq a_i \leq 100$) - los valores de las monedas. Todos los números están separados con espacios.

Salida

Un número - el número mínimo necesario de monedas.

Ejemplos

input:
2
3 3

output:
2

input:
3
2 1 2

output:
2

Nota

En el primer ejemplo tendrás que tomar 2 monedas (tú y tu gemelo tendrán sumas iguales a 6 y 0 respectivamente). Si tomas 1 moneda, obtendrás las sumas 3 y 3. Si tomas 0 monedas, obtendrás las sumas 0 y 6. Estas variantes no te satisfacen y tu suma debería ser estrictamente mayor que la suma de tu gemelo.

En el segundo ejemplo una moneda no es suficiente también. Puede selecciones las monedas con los valores 1 y 2 ó 2 y 2. En cualquier caso, el número mínimo de monedas es igual a 2.