{"problem":{"name":"DEGwer's Doctoral Dissertation","description":{"content":"DEGwer's doctoral dissertation consists of $N$ pages. Currently, there are $K$ typos in this doctoral dissertation, and the $i$\\-th typo $(i = 1, \\ldots, K)$ is on page $A_i$. To submit the doctoral d","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"1202Contest_a"},"statements":[{"statement_type":"Markdown","content":"DEGwer's doctoral dissertation consists of $N$ pages. Currently, there are $K$ typos in this doctoral dissertation, and the $i$\\-th typo $(i = 1, \\ldots, K)$ is on page $A_i$.\nTo submit the doctoral dissertation, it is necessary to correct the typos so that no consecutive $T$ pages contain multiple typos. Please help busy DEGwer, who is preparing this contest, by determining the minimum number of typos that need to be corrected in order to submit the doctoral dissertation.\n\n## Constraints\n\n*   $1 \\leq N \\leq 2 \\times 10^5$\n*   $1 \\leq K \\leq 2 \\times 10^5$\n*   $1 \\leq T \\leq N$\n*   $1 \\leq A_i \\leq N \\ \\ (1 \\leq i \\leq K)$\n\n## Input\n\nThe input is given from Standard Input in the following format:\n\n$N \\ K \\ T$ \n$A_1 \\ A_2 \\ \\dots \\ A_K$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"1202Contest_a","tags":[],"sample_group":[["5 4 3\n1 2 4 5","2\n\nDEGwer's doctoral dissertation consists of $5$ pages, with one typo each on the $1$st, $2$nd, $4$th, and $5$th pages.\nFor example, if the typos on the $1$st and $4$th pages are corrected, then no consecutive $3$ pages will have multiple typos. On the other hand, it can also be confirmed that it is impossible to meet this condition by correcting only one typo. Therefore, output $2$ as the minimum number of typos to be corrected."],["4 8 2\n1 1 1 1 1 4 2 2","6\n\nThere may also be multiple typos on a single page."],["5 2 3\n4 1","0\n\nThere may be no need to correct any typos."]],"created_at":"2026-03-03 11:01:13"}}