← 返回 amazon 的题目列表Minimum Cost to Make Equal Values Contiguous
类型：online_judge
Problem: Minimum Cost to Make Equal Values Contiguous
An Amazon warehouse has n products in a fixed order. The quality of the i-th product is quality[i]; quality values may be negative.
An inventory is optimal if all occurrences of every distinct quality value form one contiguous subarray. In other words, for any value v, there must not exist i < j < k such that quality[i] = quality[k] = v and quality[j] != v.
You may perform the following operation any number of times:
Choose two quality values x and y.
Replace every occurrence of x in the current array with y.
The cost of this operation is the number of products currently having quality x.
Return the minimum total cost required to make the inventory optimal.
Input Format
First line: integer n
Second line: n integers quality[0], quality[1], ..., quality[n-1]
Output Format
Print one integer: the minimum total cost.
Constraints
1 <= n <= 2 * 10^5
-10^9 <= quality[i] <= 10^9
Example 1
Input:
7
7 7 5 7 3 5 3
Output:
4
One optimal sequence is to replace all 5s with 7 at cost 2, then replace all 3s with 7 at cost 2.
Example 2
Input:
5
1 2 1 3 3
Output:
1
Example 3
Input:
6
1 1 2 2 3 3
Output:
0
Example
Input
7
7 7 5 7 3 5 3
Output
4