← 返回题目列表

AtCoder · 1202Contest_a

A. DEGwer 的博士论文

中文机器翻译题面 查看原题

分数: 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

可能不需要更正任何拼写错误。