Substituição de páginas: OTM/OPT

O objetivo deste exercício é escrever uma aplicação que simule o funcionamento do algoritmo Ótimo (OTM/OPT) de substituição de páginas usados em sistemas operacionais.

Neste exercício, a sua aplicação receberá uma sequência de números inteiros da entrada padrão:

• o primeiro parâmetro representa a quantidade de quadros de memória disponíveis na RAM;

• o segundo parâmetro representa a quantidade de páginas referenciadas durante a execução de um processo;

• os demais números representam a sequência de referências a páginas, sempre um número separado por linha.

Como saída, a aplicação deverá indicar a quantidade de faltas de páginas (page faults) necessárias para acomodar as páginas nos quadros disponíveis.

Importante: o algoritmo Ótimo é o único capaz de gerar a menor quantidade possível de faltas de páginas, porém não possui implementação viável em sistemas práticos, pois necessita conhecer previamente todo o padrão de acesso dos processos.

Entrada

A entrada é composta por uma sequência de inteiros separados por linhas. A primeira linha contém um número inteiro $Q$ ( $1 \leq Q \leq 10^5$ ) representando a quantidade de quadros disponíveis na memória RAM, a segunda linha contém um número inteiro $N$ ( $3 \leq N \leq 10^5$ ) indicando a quantidade de referências às páginas feitas pelo processo. A partir da terceira linha, são apresentados $N$ números $P_i$ ( $1 \leq P_i \leq 10^6$ ), cada um separado em sua respectiva linha, representando a página que é acessada pelo processo.

Saída

Para cada sequência de teste de acesso a páginas, você deverá imprimir uma única linha contendo a quantidade de quadros page faults.

Exemplo de Entrada

4
12
1
2
3
4
1
2
5
1
2
3
4
5

Exemplo de Saída

6

Exemplo de Entrada

20
3
7
0
1
2
0
3
0
4
2
3
0
3
2
1
2
0
1
7
0
1

Exemplo de Saída

9