Substituição de páginas: FIFO

O objetivo deste exercício é escrever uma aplicação que simule o funcionamento de algoritmos 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:

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. Neste exercício, utilizaremos a heurística FIFO para reposicionar as páginas.

Entrada

A entrada é composta por uma sequência de inteiros separados por linhas. A primeira linha contém um número inteiro QQ ( 1Q1051 \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 NN ( 3N1053 \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 NN números PiP_i ( 1Pi1061 \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

10

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

15