Fewest global replacements to group equal values

You are given an integer array arr of length n. In one operation you pick two different values x and y that both currently appear in arr, and you change every occurrence of x into y.

An array is blocked when the copies of each value sit next to each other. That means no value appears, then gives way to something else, then appears again.

Return the minimum number of operations needed to make arr blocked. Return 0 if it already is.

def min_merge_operations(arr: list[int]) -> int

Constraints

• 0 <= n <= 10^5
• -10^9 <= arr[i] <= 10^9

Example 1

arr = [5, 8, 5, 6]
output: 1

Change every 8 into 5, which gives [5, 5, 5, 6]. That array is blocked.

Example 2

arr = [3, 1, 3, 2, 4, 2, 4]
output: 2

Change 1 into 3, then change 4 into 2. The result is [3, 3, 3, 2, 2, 2, 2]. One operation is not enough, because both {3,1} and {2,4} interleave.

Follow-up: also return one optimal list of (x, y) operations.