내성적 캐싱

분산 시스템에서는 필요한 데이터가 늘 다른 곳에 있고, 네트워크로 데이터를 가져오는 데에는 시간과 대역폭이 든다. 이 문제는 캐시를 두어 완화할 수 있다. 노드가 일부 자원을 로컬에 저장해 두면, 같은 자원이 다시 필요할 때 다른 노드에 요청하지 않고 자신의 캐시에서 바로 꺼내 쓸 수 있다.

그러나 캐시는 금세 가득 차기 마련이라, 어느 시점에는 새 객체를 넣을 공간을 만들기 위해 기존 객체를 내보내야(eviction) 한다. 어떤 객체를 내보낼지 고르는 일은 쉽지 않으며, 선택할 수 있는 알고리즘도 여러 가지다.

어느 연구진이 내성적 캐싱(Introspective Caching) 이라는 새 알고리즘을 고안했다. 이 알고리즘에는 앞일을 내다보는 작은 도우미가 함께한다. 도우미는 앞으로 어떤 객체가 어떤 순서로 접근될지 정확히 알고 있어서, 어떤 객체를 캐시에서 내보낼지 항상 최적으로 결정한다. 여기서 최적이란 객체가 캐시로 읽혀 들어오는 횟수를 최소화한다는 뜻이다.

모든 객체 접근은 캐시를 거친다. 즉 어떤 객체에 접근할 때 그 객체가 캐시에 없으면 반드시 캐시에 넣어야 한다. 모든 객체의 크기는 같고, 시스템에는 쓰기 연산이 없으므로 캐시에 담긴 객체는 항상 유효하다. 시스템이 시작될 때 캐시는 비어 있다.

주어진 접근 순서에 대해 이 최적 전략이 객체를 캐시로 읽어 들이는 최소 횟수를 구하여라.

첫째 줄에 공백으로 구분된 세 정수가 주어진다. 차례대로 캐시에 들어갈 수 있는 객체 수 $c$ ($0 < c \le 10000$), 시스템에 존재하는 서로 다른 객체 수 $n$ ($c \le n \le 100000$), 그리고 발생하는 접근 횟수 $a$ ($0 \le a \le 100000$) 이다.

이어지는 $a$개의 줄에는 각각 $0$ 이상 $n-1$ 이하의 정수 하나가 주어지며, 이는 접근되는 객체를 나타낸다. 첫 번째 줄이 첫 번째 접근, 마지막 줄이 마지막 접근에 해당한다.

입력에 나열된 접근들을 처리하기 위해 객체를 캐시로 읽어 들여야 하는 최소 횟수를 한 줄에 출력한다.