oj mrJudge
Toggle navigation
  • Login
    • Forget Password
      Login
User Image

Hello, Stranger

Guest
  • Analysis Mode
  • Problems
    • All Problems
    • Latest Problems
  • Join Us Now
  • Registration
  • Contact Us
  • Infomation
  • About
    • Terms of Use
    • Technical Specifications
    • Credits

goodseq Batch , stdin/stdout

Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

goodseq.html

Title

Problem Statement

You are given a sequence of positive integers of length N, a = (a1, a2, ..., aN). Your objective is to remove some of the elements in a so that a will be a good sequence.

Here, an sequence b is a good sequence when the following condition holds true:

  • For each element x in b, the value x occurs exactly x times in b.

For example, (3, 3, 3), (4, 2, 4, 1, 4, 2, 4) and () (an empty sequence) are good sequences, while (3, 3, 3, 3) and (2, 4, 1, 4, 2) are not.

Find the minimum number of elements that needs to be removed so that a will be a good sequence.

Constraints

  • 1 ≤ N ≤ 105
  • ai is an integer.
  • 1 ≤ ai ≤ 109

Input

Input is given from Standard Input in the following format:

N
a1 a2 ... aN

Output

Print the minimum number of elements that needs to be removed so that a will be a good sequence.

Sample Input 1

4
3 3 3 3

Sample Output 1

1

We can, for example, remove one occurrence of 3. Then, (3, 3, 3) is a good sequence.

Sample Input 2

5
2 4 1 4 2

Sample Output 2

2

We can, for example, remove two occurrences of 4. Then, (2, 1, 2) is a good sequence.

Sample Input 3

6
1 2 2 3 3 3

Sample Output 3

0

Sample Input 4

1
1000000000

Sample Output 4

1

Remove one occurrence of 109. Then, () is a good sequence.

Sample Input 5

8
2 7 1 8 2 8 1 8

Sample Output 5

5

Tags

Data Structure

Subtasks and Limits

Subtask Score #TC Time Memory Scoring
1100181s256MBMinimum
2051s256MBMinimum

Judge Compile Command

g++-8 ans.cpp -o goodseq -Wall -Wshadow -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512

Accepted Submissions

subIDUserTimeMax Time

Past Submissions

subIDUserTimeScore
mrJudge 09.05.20
Copyright © 2020 mrJudge. All rights reserved.