Problem Description

Xiao Lan is collecting a sticker album. There are $N$ types of stickers, numbered $1, 2, \dots, N$. He will receive $M$ stickers in order, where the $i$-th sticker has number $A_i$.

When processing a sticker:

• If Xiao Lan has not collected the sticker numbered $A_i$ yet, he pastes this sticker into the album.
• If Xiao Lan has already collected the sticker numbered $A_i$, this duplicate sticker becomes $1$ exchange coupon.

Whenever the number of exchange coupons reaches $K$, Xiao Lan must immediately spend $K$ exchange coupons to obtain the currently smallest-numbered sticker that has not been collected yet, and paste it into the album.

If Xiao Lan has already collected all $N$ types of stickers, then the stickers received afterward will no longer change the number of collected sticker types.

Please compute how many types of stickers Xiao Lan has collected in total after processing all $M$ stickers.

Input Format

The first line contains three integers $N, M, K$, representing the number of sticker types, the number of stickers received, and the number of exchange coupons needed for each exchange.

The second line contains $M$ integers $A_1, A_2, \dots, A_M$, representing the sticker numbers Xiao Lan receives in order.

Output Format

Output one line containing one integer, representing the number of sticker types Xiao Lan has collected after processing all stickers.

6 10 3
2 4 2 2 5 4 1 3 3 6

6

5 7 2
4 4 2 4 2 5 5

5

Hint

Sample Explanation 1

The first two stickers are numbered $2, 4$, and both can be pasted directly into the album. The $3$-rd and $4$-th stickers are both numbered $2$, which are duplicates, so Xiao Lan gets $2$ exchange coupons.

The $5$-th sticker is numbered $5$ and is pasted directly into the album. The $6$-th sticker is numbered $4$, which gives $1$ more exchange coupon. Now there are $3$ exchange coupons in total, so he must exchange immediately. The smallest number not yet collected is currently $1$, so he obtains the sticker numbered $1$.

He then continues processing the remaining stickers, and finally can collect all stickers numbered $1$ to $6$. The answer is $6$.

Sample Explanation 2

The $2$-nd and $4$-th stickers are both duplicates of the already collected sticker numbered $4$. After processing the $4$-th sticker, there are $2$ exchange coupons, so he must exchange for the current smallest missing sticker $1$.

Later, duplicate stickers numbered $2$ and $5$ produce $2$ more exchange coupons, and in the end he exchanges to obtain the sticker numbered $3$. After processing everything, $1,2,3,4,5$ have all been collected, so the answer is $5$.

Constraints and Notes for Test Cases

For $30\%$ of the test cases, $N, M \le 200$.

For $60\%$ of the test cases, $N, M \le 5000$.

For all test cases, $1 \le N, M, K \le 2 \times 10^5$, and $1 \le A_i \le N$.

Translated by ChatGPT 5