Students are standing in a fixed row. The marks received by the ith student are stored in marks.get(i).

The row is properly grouped when all students having the same marks stand together in one continuous group.

The students cannot change positions, but their recorded marks can be updated. Find the minimum number of student records that must be changed to properly group the row.

Rules

• In one operation, choose two different values oldMarks and newMarks.
• Change the marks of every student currently having oldMarks to newMarks.
• The cost of the operation is the number of student records changed.
• Changing only some students having oldMarks is not allowed.
• Any number of operations may be performed, including zero.
• The positions of the students never change.
• A marks value appearing only once already forms a valid group.
• Marks may be negative because of penalties.

Class

StudentMarksOrganizer

Constructor

StudentMarksOrganizer

StudentMarksOrganizer()

• Creates a new student marks organizer.

Method

minimumMarkChanges

int minimumMarkChanges(List<Integer> marks)

• marks.get(i) contains the marks of the ith student.
• Returns the minimum total number of student records that must be changed.

Constraints

• 1 ≤ marks.size() ≤ 100,000
• -1,000,000,000 ≤ marks.get(i) ≤ 1,000,000,000
• marks is non-null.

Expected Efficiency

• The method should run in O(n) expected time.
• The method may use O(n) additional space.

Example 1

minimumMarkChanges(marks = List.of(80, 60, 80, 70, 70, 90))

Output: 1

Change every mark of 60 to 80. The marks become [80, 80, 80, 70, 70, 90].

Example 2

minimumMarkChanges( marks = List.of(50, 70, 50, 90, 70, 40, 90, 40))

Output: 6

Change every 70, 90, and 40 to 50. Each operation changes two records, so the total cost is 6.

Example 3

minimumMarkChanges(marks = List.of(100, 100, -5, -5, 75))

Output: 0

Students having the same marks are already together.

Example 4

minimumMarkChanges( marks = List.of(60, 40, 60, 90, 75, 90, 30, 30))

Output: 2

Change every 40 to 60 and every 75 to 90. The marks become [60, 60, 60, 90, 90, 90, 30, 30].