Power Strip Scheduling

Interview

Time limit2sMemory limit128 MB

Summary
Simulate plugging devices into a strip with N outlets and, when full, evict the device whose next use is farthest away (or never used again), counting total unplugs.
Level

Medium5 of 10

Topics
Greedy, Simulation, Array
Solved
No attempts yet

Problem

A power strip has N outlets, and the numbers of the electrical devices that will be used over the next K uses are given in order. To use a device, its plug must be inserted into the power strip. If an outlet is empty, a new plug can be inserted. If every outlet is occupied and the needed device is not plugged in, one currently plugged-in device must be unplugged. Given the entire usage order, find the minimum number of times a plug must be unplugged.

Input

The first line contains the number of outlets N (1 ≤ N ≤ 100) and the total number of device uses K (1 ≤ K ≤ 100). The second line contains K natural numbers in usage order. Each number is a device identifier and is at most K. All integers in the input are separated by spaces.

Output

Print the minimum number of times a plug must be unplugged.

Examples1

  1. Example 1

    Input
    2 7
2 3 2 3 1 2 7
    Expected output
    2