Linea della limonata#10385
È una calda giornata d'estate in fattoria, e Farmer John sta servendo limonata alle sue mucche! Tutte le mucche (numerate per comodità da a ) amano la limonata, ma alcune la amano più di altre. In particolare, la mucca è disposta ad aspettare in fila dietro al massimo w_i mucche per ottenere la sua limonata. Proprio ora, tutte le mucche sono nei campi, ma non appena Farmer John suona la sua campanella, esse si precipiteranno immediatamente verso il suo chiosco di limonata. Tutte arriveranno prima che lui inizi a servire la limonata, e non ci saranno due mucche che arriveranno nello stesso momento. Inoltre, quando la mucca arriva, si unisce alla fila se e solo se ci sono al massimo w_i mucche già in fila.
Farmer John vuole preparare della limonata in anticipo, ma non vuole essere dispendioso. Il numero di mucche che si uniscono alla fila può dipendere dall'ordine in cui esse arrivano. Aiutalo a trovare il numero minimo possibile di mucche che si uniscono alla fila.
La prima riga contiene un intero n~(1 \le n \le 10^5). La seconda riga contiene interi w_1, w_2, \ldots, w_n~(0 \le w_i \le 10^9).
Stampa un intero — il numero minimo di mucche che si uniscono alla fila, su tutti i possibili ordini in cui le mucche possono arrivare.
Esempio 1
In questo esempio, solo mucche possono finire in fila, e questo è il numero più piccolo possibile. Supponiamo che le mucche con w = 7 e w = 400 arrivino per prime e si uniscano alla fila. Poi la mucca con w = 1 arriva e se ne va, poiché ci sono già mucche in fila. Infine, le due mucche con w = 2 arrivano: la prima si unisce alla fila, e la seconda se ne va.