Seguro que todos en IslaGrande han oído hablar alguna vez de compañías como Google, Yahoo o Microsoft. Qué tienen todas en común, fueron creadas por dos jóvenes genios de la informática y con ideas emprendedoras. Este es el caso de Bitman y el Teacher. Ellos tuvieron una idea genial y crearon la Asociación Caribeña de Monstruos (ACM por sus siglas en español). Esta compañía dirige varios establecimientos donde tienen cautivas diversas criaturas extrañas endémicas del Caribe, una especie de zoo para monstruos. El negocio es un exitazo y ya tienen sedes en todo el país. Las ganancias se las reparten por igual y piensan crear sucursales en el extranjero.

Pero todo es demasiado bueno para ser verdad. Resulta que nuestros amigos, al igual que todos, no son perfectos y tienen sus detallitos. Como consecuencia de sus recientes excentricidades la empresa ha perdido mucho dinero y es probable que quiebre. Ellos han conversado y han decidido enderezar su camino. Pero ya el daño esta hecho y algunos zoos deben disminuir la cantidad de monstruos pues no tienen para mantener a tantos.

Cada zoo posee ~N~ monstruos y cada monstruo tiene una fuerza interna ~s_i~. Para disminuir la cantidad de criaturas ellos poseen en cada zoo una inyección de locura, que si se la inyectan a un monstruo ~i~, este se puede comer a un monstruo ~j~ si ~(s_j \leq 2*s_i)~, y su fuerza interna pasaría a ser ~s_i+s_j~ , y luego podría seguir comiendo. En varios zoos ha pasado que al inyectar a un monstruo este se ha comido a todos los demás, lo que es malo para el negocio ya que nadie va a un zoo que tenga un solo animal.

Ayude a los amigos a determinar cuántos de estos monstruos podrían acabar comiéndose a todos los demás si los inyectan.

Entrada

La primera línea de entrada contiene el entero ~N~, la cantidad de monstruos del zoo. La siguiente línea contiene ~N~ enteros separados por un espacio ~s_1, s_2 ... s_n~, la fuerza interna de cada monstruo.

Salida

La única línea de salida contiene un solo entero ~m~, la cantidad de monstruos que si los inyectan pueden acabar comiéndose a todos los demás.

Subtareas

• Subtarea 1 (10 puntos): ~1 \leq N \leq 10~
• Subtarea 2 (15 puntos): ~1 \leq N \leq 16~ .
• Subtarea 3 (30 puntos): ~1 \leq N \leq 5000~ .
• Subtarea 4 (45 puntos): ~1 \leq N \leq 10^5~ .

Para todas las subtareas ~1 \leq s_i \leq 10^9~.

Ejemplo de Entrada

5              
37 1 13 3 2

Ejemplo de Salida

2

Explicación del ejemplo: El 1er monstruo se puede comer a cualquiera en el orden que quiera. El 2do monstruo se puede comer al 5to y luego al 4to, pero ya no puede seguir comiendo. El 3er monstruo se puede comer al 2do, 5to y 4to en el orden que quiera y luego comerse al 1ro. El 4to monstruo se puede comer al 2do y al 5to en el orden que quiera pero no puede seguir comiendo. El 5to monstruo se puede comer al 2do y al 4to en el orden que quiera pero no puede seguir comiendo. Solamente el 1ro y el 3er monstruo se pueden comer a todos los demás.