#K55612. Maximum Diverse Dishes
Maximum Diverse Dishes
Maximum Diverse Dishes
Alice has n different ingredients, and each ingredient i is available in a quantity ai. She wants to prepare as many diverse dishes as possible. A dish is called diverse if it uses each ingredient at most once without repeats.
Formally, given a sorted list of ingredients' quantities \(a_1 \le a_2 \le \cdots \le a_n\), Alice can prepare a dish only if there exists an ingredient whose available units are greater than the number of dishes already prepared. In other words, if she has prepared \(d\) dishes, she can only use an ingredient if its quantity is greater than \(d\). Your task is to determine the maximum number \(d\) of diverse dishes that Alice can prepare.
Example:
Input: n = 5, ingredients = [3, 2, 3, 1, 4] Sorted ingredients: [1, 2, 3, 3, 4] Diverse dish count = 4
Note: All comparisons and calculations involving ingredient quantities follow the strict inequality \(a_i > d\) where \(d\) is the current count of dishes prepared.
inputFormat
The first line contains an integer n (the number of ingredients).
The second line contains n space-separated integers, representing the quantities of each ingredient.
Input is read from standard input (stdin).
outputFormat
Output a single integer representing the maximum number of diverse dishes Alice can prepare.
The result should be printed to standard output (stdout).
## sample5
3 2 3 1 4
4
</p>