← 返回题目列表

Codeforces · 1190/A

A. 时风和丢弃物品

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

最近,时风发现了一个有趣的游戏。 Tokitsukaze 在游戏开始时拥有 $$$n$$$ 物品。然而,她认为物品太多了,所以现在她想丢弃其中$$$m$$$ ($$$1 \le m \le n$$$) 个特殊物品。

这些 $$$n$$$ 项目标有从 $$$1$$$ 到 $$$n$$$ 的索引。一开始,索引为$$$i$$$的项目被放置在第$$$i$$$位置。项目按顺序分为几页,使得每页恰好包含 $$$k$$$ 个位置,并且最后一页上的最后一个位置可以留空。

时风会执行以下操作:聚焦于第一个包含至少一个特殊项目的特殊页面,并且一次,时风会丢弃该页面上的所有特殊项目。当一个项目被丢弃或移动后,它的旧位置将是空的,然后它下面的项目(如果存在)将向上移动到这个空位置。移动可能会将许多物品向前移动,甚至进入之前的页面,因此时风会一直等待,直到所有物品停止移动,然后重复执行该操作(即检查特殊页面并丢弃特殊物品),直到没有物品需要丢弃为止。

考虑语句中的第一个示例:$$$n=10$$$、$$$m=4$$$、$$$k=5$$$、$$$p=[3, 5, 7, 10]$$$。有两页。最初,第一页是特殊的(因为它是包含特殊项目的第一页)。因此,Tokitsukaze 丢弃索引为 $$$3$$$ 和 $$$5$$$ 的特殊项目。之后,第一页仍然很特别。它包含$$$[1, 2, 4, 6, 7]$$$,时风丢弃索引为$$$7$$$的特殊项目。之后,第二页是特殊的(因为它是包含特殊项目的第一页)。它包含$$$[9, 10]$$$,时风丢弃索引为$$$10$$$的特殊项目。

Tokitsukaze 想知道她总共要做的手术次数。

输入

第一行包含三个整数 $$$n$$$、$$$m$$$ 和 $$$k$$$ ($$$1 \le n \le 10^{18}$$$, $$$1 \le m \le 10^5$$$, $$$1 \le m, k \le n$$$) — 物品数量、要丢弃的特殊物品数量和每页中的位置。

第二行包含 $$$m$$$ 不同的整数 $$$p_1, p_2, \ldots, p_m$$$ ($$$1 \le p_1 < p_2 < \ldots < p_m \le n$$$) — 应丢弃的特殊项目的索引。

输出

打印单个整数 — Tokitsukaze 总共执行的操作数。

示例

输入 #1

10 4 5
3 5 7 10

输出 #1

3

输入 #2

13 4 5
7 8 9 10

输出 #2

1

注意

对于第一个示例:

- 在第一次操作中,Tokitsukaze 会专注于第一页 $$$[1, 2, 3, 4, 5]$$$ 并丢弃索引为 $$$3$$$ 和 $$$5$$$ 的项目;
- 在第二次操作中,时风会专注于第一页 $$$[1, 2, 4, 6, 7]$$$ 并丢弃索引为 $$$7$$$ 的项目;
- 在第三次操作中,时风会专注于第二页 $$$[9, 10]$$$ 并丢弃索引为 $$$10$$$ 的项目。

对于第二个示例,Tokitsukaze 会专注于第二页 $$$[6, 7, 8, 9, 10]$$$ 并立即丢弃所有特殊项目。