fifo_cache.cpp

#include <iostream>
#include <queue>
#include <set>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int m, n;
    cin >> m >> n;

    queue<int> fifo;
    set<int> memory;
    int count = 0;

    for (int i = 0; i < n; i++) {
        int word;
        cin >> word;

        if (memory.count(word)) {
            // word already in memory
            continue;
        }

        // need to look up external memory
        count ++;

        if ((int)memory.size() == m) {
            // memory is full, remove earliest stored word
            int oldest = fifo.front();
            fifo.pop();
            memory.erase(oldest);
        }

        // store new word in memory
        fifo.push(word);
        memory.insert(word);
    }
    cout << count << endl;
    return 0;
}