最近,时风发现了一个有趣的游戏。 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]$$$ 并立即丢弃所有特殊项目。