Multitap Scheduling 2
InterviewTime limit2sMemory limit512 MB
Given a power strip with N holes and a usage sequence, find the minimum number of unplugs needed using the optimal offline replacement rule.
- Level
Medium7 of 10
- Topics
- Greedy, Hash map, Simulation, Array
- Solved
- No attempts yet
Problem
Junkyu, who lives in a dormitory, uses a single power strip. He uses several electric appliances, such as a keyboard, a hair dryer, a phone charger, and a digital camera charger, and he has to put up with the inconvenience of unplugging and replugging their plugs. So Junkyu analyzed his daily routine, found out the order in which he uses his electric appliances, and based on that, he wants to devise a way to minimize the number of times he unplugs a plug, to make his living environment more comfortable.
For example, suppose he uses a 3-hole power strip and the order in which he uses the electric appliances is given as follows.
- keyboard
- hair dryer
- phone charger
- digital camera charger
- keyboard
- hair dryer
He plugs the keyboard, the hair dryer, and the phone charger into the power strip in that order, and then, before plugging in the digital camera charger, it is optimal to unplug the phone charger, so he only needs to unplug a plug once.
Input
The first line gives the number of holes in the power strip N (1 ≤ N ≤ 500,000) and the total number of times the electric appliances are used K (1 ≤ K ≤ 500,000) as integers. The second line gives the names of the electric appliances as natural numbers less than or equal to K, in the order of use. All integers on each line are separated by whitespace.
Output
Print the minimum number of times he unplugs a plug.