Duplicate Flight Removal

You are given a list of flight numbers. Some flight numbers may appear more than once. Your task is to determine the minimum number of flight numbers that must be removed so that no flight number appears more than once.

Note: A flight number is a string which typically begins with an airline prefix followed by digits. You should count and remove duplicates (keeping only one instance of each distinct flight number).

For example, if the input contains "PA123", "PA124", "PA123", "AA100", "AA100", then the answer is 2 because one duplicate from "PA123" and one from "AA100" must be removed.

The solution should read the input from stdin and write the answer to stdout.

inputFormat

The first line contains an integer n representing the number of flight numbers. The next n lines, each contain a flight number (a non-empty string without spaces).

outputFormat

Output a single integer which is the minimum number of flight numbers that must be removed such that each flight number appears only once.

5
PA123
PA124
PA123
AA100
AA100

2