신발

Lana에게는 번호가 $1$부터 $n$까지 매겨진 신발 $n$켤레가 있다. 모든 신발은 긴 신발장에 보관되어 있다. 처음에 번호 $1$번 신발은 신발장 맨 위(현관 가까이)에 있고, 번호 $n$번 신발은 맨 아래(현관에서 먼 쪽)에 있다.

다음 $q$일 중 $i$번째 날에 Lana는 번호 $a_i$번 신발을 신고 싶어 한다. 신발장에서 신발 한 켤레를 꺼내려면 먼저 그보다 현관 쪽에 있는 신발들을 모두 꺼내야 한다. 원하는 신발을 꺼낸 뒤에는 나머지 신발을 원래 순서대로 신발장에 다시 넣는다. 신발장에서 신발 한 켤레를 꺼내는 데 $1$초가 걸리며, 신발을 다시 넣는 데는 추가 시간이 들지 않는다.

하루가 끝나면 Lana는 신발을 벗고 다음 중 하나를 한다.

• 신발장 맨 위에 다시 넣는다.
• 현관 복도에 둔다. 단, 복도에 빈자리가 있어야 한다.

현관 복도에는 최대 $m$켤레까지 둘 수 있다. 또한 Lana는 언제든지(원하는 신발을 꺼내는 중인 경우는 제외하고) 복도의 신발을 신발장 맨 위로 옮길 수 있다. 그날 시작할 때 원하는 신발이 이미 복도에 있으면, Lana는 꺼내는 시간 없이 바로 신을 수 있다.

Lana는 바쁘며, 신발을 꺼내는 데 쓰는 총 시간을 최소화하고 싶어 한다. 다음 $q$일 동안 신발을 꺼내는 데 필요한 최소 시간을 구하시오.

첫 줄에 신발의 수 $n$, 복도의 칸 수 $m$, 날짜 수 $q$가 주어진다 ($1 \le n \le 2 \cdot 10^5$, $0 \le m \le 2 \cdot 10^5$, $1 \le q \le 10^6$).

둘째 줄에는 $q$개의 정수 $a_i$($1 \le a_i \le n$)가 주어지며, $a_i$는 $i$번째 날에 Lana가 신고 싶은 신발의 번호이다.

모든 $q$일 동안 신발을 꺼내는 데 걸리는 최소 시간을 한 줄에 출력한다.

첫 번째 예제에 대한 설명이다.

첫째 날 Lana는 신발장에서 번호 $2$번 신발을 꺼낸다. 이 작업에 $2$초가 걸린다. 하루가 끝나면 그 신발을 복도에 두고 계속 그대로 둔다.

이제 신발장에서 $1$번 신발을 꺼내야 할 때마다 $1$초가 걸린다. 반면 $2$번 신발이 필요하면 복도에서 바로 신을 수 있어 시간이 들지 않는다.

Lana가 신발을 꺼내는 데 쓰는 총 시간은 $2 + 1 + 0 + 1 + 0 + 1 = 5$초이다.