Minimum Enough Groups - Repovive Starter Round 3 | Repovive

12D. Minimum Enough Groups

2000 pts1s256 MB

You are given $n$ people, numbered from $1$ to $n$ .

Person $i$ has an integer $a_i$ . They are happy only if the group containing them has at least $a_i$ people.

You want to form some pairwise disjoint groups. Each person can be used in at most one group, and some people may be left unused.

A group is good if every person in it is happy.

Find the maximum possible number of good groups.

Constraints

$1 \le n \le 2 \times 10^5$
$1 \le a_i \le n$

Input

n

a_1 \quad a_2 \quad \cdots \quad a_n

Output

ans

Samples

Input

5
1 1 1 1 1

Explanation

Each person can be used as a separate group of size $1$ , so we can make $5$ good groups.

Output

Input

5
2 2 3 3 3

Explanation

One optimal grouping is $[1, 2]$ and $[3, 4, 5]$ . The first group has size $2$ , and the second group has size $3$ , so all used people are happy.

Output

Input

7
3 1 2 4 2 4 4

Explanation

One optimal grouping is $[2]$ , $[3, 5]$ , and $[1, 4, 6, 7]$ . Their sizes are $1$ , $2$ , and $4$ , and every person in these groups has a requirement at most the size of their group.

Output

You are given $n$ people, numbered from $1$ to $n$ .

Person $i$ has an integer $a_i$ . They are happy only if the group containing them has at least $a_i$ people.

You want to form some pairwise disjoint groups. Each person can be used in at most one group, and some people may be left unused.

A group is good if every person in it is happy.

Find the maximum possible number of good groups.

$1 \le n \le 2 \times 10^5$
$1 \le a_i \le n$

n

a_1 \quad a_2 \quad \cdots \quad a_n

ans

Each person can be used as a separate group of size $1$ , so we can make $5$ good groups.

One optimal grouping is $[1, 2]$ and $[3, 4, 5]$ . The first group has size $2$ , and the second group has size $3$ , so all used people are happy.

One optimal grouping is $[2]$ , $[3, 5]$ , and $[1, 4, 6, 7]$ . Their sizes are $1$ , $2$ , and $4$ , and every person in these groups has a requirement at most the size of their group.

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

12D. Minimum Enough Groups

Constraints

Input

Output

Samples

12D. Minimum Enough Groups

Constraints

Input

Output

Samples