Contractació P21012

Statement

Una companyia vol contractar nous treballadors. La companyia ha ordenat els $n$ candidats de més valuosos a menys valuosos. Per a cada candidat $i$ , saben el sou $s_i$ que demana. Volen triar els candidats de manera que si un candidat és més valuós que un altre, cobri estrictament més. Quina és la màxima quantitat de nous treballadors que es pot contractar?

Entrada

L’entrada consisteix en diversos casos, cadascun amb una $n$ entre 1 i $10^5$ , seguida de $s_1, \dots, s_n$ . Totes les $s_i$ estan entre 1 i $10^9$ .

Sortida

Per a cada cas, escriviu quants treballadors es podran contractar.

Observació

La solució esperada té cost millor que $\Theta(n^2)$ .

Public test cases

Input

1  100
3  42 42 42
2  1000000000 1
8  23 16 19 5 12 16 12 10

Output

Information

Author: Salvador Roura
Language: Catalan
Official solutions: C++
User solutions: C++