{"raw_statement":[{"iden":"problem statement","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."},{"iden":"constraints","content":"*   $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)$"},{"iden":"input","content":"The input is given from Standard Input in the following format:\n\n$N \\ K \\ T$ \n$A_1 \\ A_2 \\ \\dots \\ A_K$"},{"iden":"sample input 1","content":"5 4 3\n1 2 4 5"},{"iden":"sample output 1","content":"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."},{"iden":"sample input 2","content":"4 8 2\n1 1 1 1 1 4 2 2"},{"iden":"sample output 2","content":"6\n\nThere may also be multiple typos on a single page."},{"iden":"sample input 3","content":"5 2 3\n4 1"},{"iden":"sample output 3","content":"0\n\nThere may be no need to correct any typos."}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}