Food Display Arrangement
시간 제한1초메모리 제한1024 MB
음식 종류가 나열된 열에서 한 종류를 모두 왼쪽이나 오른쪽 끝으로 옮기는 동작을 반복해 같은 종류가 인접하도록 만들 때 필요한 최소 동작 수를 구한다.
문제
Your friend, Thomas, is working on Food Display Arrangements (FDA). He has all the food lined up on a long row (table). His job requires that he arranges the FDA in an aesthetically pleasing manner. An FDA is aesthetically pleasing if all the food of the same type is grouped together, i.e., all the food of the same type are next to each other. Thomas can reorganize the FDA as follows: pick up all the food of one type and place it on either end of the table, i.e., place it at the beginning of the table or at the end of the table. Thomas wants to know the minimum number of reorganization steps needed to make the FDA aesthetically pleasing. Note that you don’t need to tell him the specific steps, only the least number of steps.
Given a display of food by their types, determine the minimum number of times necessary to move all food of the same type to the end or the beginning of the display to ensure that all food of the same type is grouped together. Assume that the display can be extended at the ends to contain any amount of moved food.
입력
The first input line contains an integer, n (1 ≤ n ≤ 100,000), representing the number of food items in the display. The next input line contains n space separated integers, ai (1 ≤ ai ≤ 1,000,000,000), representing the id of the i th food item in the display.
출력
Print the minimum number of times necessary to move all food of the same type to the beginning or the end to make the FDA aesthetically pleasing.
힌트
Explanation of the first Sample Input/Output: We can move all food of type 2 to either end and all food of type 7 to either end, for a total of 2 moves.