分数: 100 点
问题陈述
DEGwer 的博士论文包括 N 页。目前,有 K 这篇博士论文中的错别字,以及 i-第一个拼写错误 (i = 1, \ldots, K) 已在页面上 A_i.
提交博士论文,需要更正错别字,以免连续 T 页面包含多个拼写错误。 请帮助正在准备本次竞赛的忙碌的DEGwer,确定提交博士论文需要纠正的最少拼写错误数量。
约束
- 1 \leq N \leq 2 \times 10^5
- 1 \leq K \leq 2 \times 10^5
- 1 \leq T \leq N
- 1 \leq A_i \leq N \ \ (1 \leq i \leq K)
输入
输入由标准输入按以下格式给出:
N \ K \ T A_1 \ A_2 \ \dots \ A_K
输出
输出提交博士论文需要纠正的最少错别字数。
示例输入 1
5 4 3 1 2 4 5
示例输出 1
2
DEGwer 的博士论文包括 5 页,每页有一个拼写错误 1圣, 2nd, 4日,以及 5第页。
例如,如果 1圣和 4第页已更正,则不再有连续的 3 页面将有多个拼写错误。 另一方面,也可以确认仅修正一个错别字是不可能满足这个条件的。 因此,输出 2 作为要纠正的最小拼写错误数。
示例输入 2
4 8 2 1 1 1 1 1 4 2 2
示例输出 2
6
单个页面上也可能存在多个拼写错误。
示例输入 3
5 2 3 4 1
示例输出 3
0
可能不需要更正任何拼写错误。