You are given an array arr of n integers. In one operation, you choose any two distinct values x and y that appear in arr and replace every occurrence of x with y. Return the minimum number of operations needed to make the array valid.

An array is valid if every distinct value forms exactly one contiguous block. This means that for any value v, all occurrences of v must appear next to each other in a single continuous segment. Values do not all need to be the same. For example,

• [1, 1, 2, 2, 3] is valid because each distinct value appears in one contiguous block.
• [1, 2, 1, 3] is not valid because value 1 appears in two separated blocks, with value 2 between them.

If arr is already valid, return 0.

Constraints:

• 1 ≤ n ≤ 1000
• 1 ≤ arr[i] ≤ 1000

Example 1:

Input: arr = [1, 2, 1] Output: 1 Explanation: Value 1 appears at two positions with value 2 between them. Replacing every occurrence of 2 with 1 yields [1, 1, 1], where 1 forms a single contiguous block. One operation is sufficient.

Example 2:

Input: arr = [1, 2, 3, 1, 2, 3] Output: 2 Explanation: One way to make the array valid is:

• Replace every occurrence of 2 with 1, giving [1, 1, 3, 1, 1, 3].
• Replace every occurrence of 3 with 1, giving [1, 1, 1, 1, 1, 1].

Now the only remaining distinct value is 1, so it forms a single contiguous block

Example 3:

Input: arr = [1, 2, 1, 2] Output: 1