Descripción
Marquito tiene un gemelo. Tener otra persona que se parece exactamente a ti parece muy inusual. Es difícil decir si tener algo parecido a un alter ego es bueno o malo. Y si tienes un gemelo, entonces sabes muy bien cómo es.
Ahora imaginemos una mañana típica en la familia de Marquito. Aún no se ha despertado y su mamá ya se va a trabajar. Se ha apresurado tanto que casi se ha olvidado de dejarles a sus dos queridos hijos algo de dinero para comprar el almuerzo en la cafetería de la escuela. Buscó en el bolso y encontró una cierta cantidad de monedas, o para ser exactos, N monedas de valores arbitrarios A1, A2, ..., An. Pero como a la mamá de Marquito se le estaba acabando el tiempo, no dividió las monedas para cada hijo. Así que garabateó una nota pidiéndole a Marquito que dividiera el dinero en partes iguales.
Cuando Marquito se despertó, encontró las monedas de su mamá y leyó su nota. "¿Pero por qué dividir el dinero en partes iguales?" —pensó. Después de todo, su gemelo está durmiendo y no sabrá nada. Así que decidió actuar así: eligió un subconjunto de monedas para que la suma de los valores de las monedas sea estrictamente mayor que la suma de los valores de las monedas restantes que tendrá su gemelo. Sin embargo, pensó correctamente que si toma demasiadas monedas, el gemelo sospechará del engaño.
Entonces, ha decidido seguir la siguiente estrategia para evitar sospechas: tomar el número mínimo de monedas, cuya suma de valores es estrictamente mayor que la suma de los valores de las monedas restantes. Sobre esta base, determina qué cantidad mínima de monedas necesita tomar para dividirlas de la manera descrita.
Ahora imaginemos una mañana típica en la familia de Marquito. Aún no se ha despertado y su mamá ya se va a trabajar. Se ha apresurado tanto que casi se ha olvidado de dejarles a sus dos queridos hijos algo de dinero para comprar el almuerzo en la cafetería de la escuela. Buscó en el bolso y encontró una cierta cantidad de monedas, o para ser exactos, N monedas de valores arbitrarios A1, A2, ..., An. Pero como a la mamá de Marquito se le estaba acabando el tiempo, no dividió las monedas para cada hijo. Así que garabateó una nota pidiéndole a Marquito que dividiera el dinero en partes iguales.
Cuando Marquito se despertó, encontró las monedas de su mamá y leyó su nota. "¿Pero por qué dividir el dinero en partes iguales?" —pensó. Después de todo, su gemelo está durmiendo y no sabrá nada. Así que decidió actuar así: eligió un subconjunto de monedas para que la suma de los valores de las monedas sea estrictamente mayor que la suma de los valores de las monedas restantes que tendrá su gemelo. Sin embargo, pensó correctamente que si toma demasiadas monedas, el gemelo sospechará del engaño.
Entonces, ha decidido seguir la siguiente estrategia para evitar sospechas: tomar el número mínimo de monedas, cuya suma de valores es estrictamente mayor que la suma de los valores de las monedas restantes. Sobre esta base, determina qué cantidad mínima de monedas necesita tomar para dividirlas de la manera descrita.
Entrada
La primera línea contiene el número entero N (1 ≤ N ≤ 100): el número de monedas.
La segunda línea contiene una secuencia de N números enteros A1, A2, ..., An (1 ≤ Ai ≤ 100): los valores de las monedas.
Todos los números están separados por espacios.
Salida
Imprime el número único: la cantidad mínima necesaria de monedas.
Ejemplo Entrada
3 2 1 2
Ejemplo Salida
2
Ayuda
En el caso de prueba, Marquito puede elegir monedas con valores 1, 2 o 2, 2. En cualquier caso, el número mínimo de monedas es 2.