A1. 猎捕（Hunt）

时间限制： 1.5 秒
内存限制： 1024 MB
来源： National Summer Tournament in Informatics, Plovdiv, 12--14 June 2026，Group A，11--12 年级
作者： Emil Indzhev

题目描述

Elmer Fudd 正在猎兔。更准确地说，和往常一样，他想抓住 Bugs Bunny。

Bugs 藏在一片环形森林中。我们把森林看成一条首尾相接的带子，分成 $L$ 个扇区，编号为 $0$ 到 $L-1$。对于 $0\le i<L$，扇区 $i$ 与扇区 $(i+1)\bmod L$ 相邻。

Elmer 知道，在第 $0$ 天，Bugs 位于 $N$ 个不同扇区之一：

此外，每天晚上，包括第 $0$ 天晚上，Bugs 都会从当前扇区移动到一个相邻扇区：如果当前在 $P$，则移动到 $(P-1)\bmod L$ 或 $(P+1)\bmod L$。注意，他永远不会停在原地。

Elmer 在第 $H$ 天早晨到达森林，其中 $H>0$。从那以后，每天早晨，包括第 $H$ 天早晨，他都会在自己选择的一个扇区放置一个陷阱。如果 Bugs 任何时候出现在有陷阱的扇区中，无论是白天刚放下陷阱后就在该扇区，还是某天晚上移动进入该扇区，都会被抓住。

Elmer 的目标是保证迟早抓住 Bugs，并且希望使用尽可能少的陷阱。注意，Bugs 有可能在最后一个陷阱放下之后的某个更晚时间才被抓住；重要的是最终一定会被抓住。

请你编写程序 hunt，给定 $L,H$ 和可能的初始扇区列表 $P_0,\ldots,P_{N-1}$，求 Elmer 为了保证抓住 Bugs 所需的最少陷阱数。Elmer 每天至多放置一个陷阱。

实现细节

你需要实现如下函数：

long long solve(long long L, long long H, std::vector<long long> P);

参数含义如下：

• $L$：森林中的扇区数。
• $H$：Elmer 到达的日期，即他第一次放置陷阱的日期。
• $P$：Bugs 可能的初始扇区列表。

该函数在一次程序运行中会被调用恰好一次。函数需要返回一个整数：保证抓住 Bugs 所需的最少陷阱数。

约束条件

设 $N=|P|$。

• $1\le N\le 2\times 10^6$
• $1\le H\le 10^{12}$
• $2\le L\le 10^{15}$
• $0\le P_i<L$
• 若 $i\ne j$，则 $P_i\ne P_j$
• $N\le L$

子任务

样例

样例 1

输入

1 7 1
1

输出

3

样例 2

输入

5 969 44
4 108 619 887 408

输出

237

样例解释

对于样例 1，$N=1,L=7,H=1$，唯一可能的初始位置是 $P_0=1$。

一种使用 $3$ 个陷阱的最优方案如下：第 $1$ 天在扇区 $2$ 放陷阱，第 $2$ 天在扇区 $6$ 放陷阱，第 $3$ 天在扇区 $0$ 放陷阱。

过程如下：

• 第 $0$ 天晚上，Bugs 从 $1$ 移动到 $0$ 或 $2$。
• 第 $1$ 天早晨，Elmer 在 $2$ 放陷阱。如果 Bugs 在 $2$，他会立刻被抓住；剩下需要考虑 Bugs 在 $0$ 的情况。
• 第 $1$ 天晚上，Bugs 从 $0$ 移动到 $6$ 或 $1$。
• 第 $2$ 天早晨，Elmer 在 $6$ 放陷阱。类似地，只剩下 Bugs 在 $1$ 的情况需要考虑。
• 第 $2$ 天晚上，Bugs 从 $1$ 移动到 $0$ 或 $2$。如果他移动到 $2$，会立即被已经放好的陷阱抓住；剩下只需考虑他移动到 $0$ 的情况。
• 第 $3$ 天早晨，Elmer 在 $0$ 放陷阱，这也是唯一剩余的可能位置。

因此 Elmer 可以保证抓住 Bugs。注意，在这个例子中 Bugs 最晚会在第 $3$ 天被抓住，但题目只关心 Elmer 放置陷阱的天数。Bugs 也可能在最后一个陷阱放置后才被抓住。

本地 grader 输入输出格式

输入格式

• 第 $1$ 行：三个整数 $N,L,H$。
• 第 $2$ 行：$N$ 个整数 $P_0,P_1,\ldots,P_{N-1}$。

输出格式

• 第 $1$ 行：调用 solve 后返回的值。