CF767B The Queue

终于！Vasya 已经成年，这意味着他终于可以办理护照了！为了办理护照，他需要去护照办公室，但事情并没有那么简单。护照办公室只有一位接待员，人们可以在开门前很久就排队。Vasya 想明天去护照办公室。 他知道接待员将在午夜后 $t_s$ 分钟开始工作，并在午夜后 $t_f$ 分钟结束工作（因此接待员最后工作的时刻是 $t_f-1$ 分钟）。接待员为队列中的每个人提供服务的时间恰好为 $t$ 分钟。如果接待员在 $t$ 分钟内下班，则只会服务现在正在服务的那位访客，其余人无法被接待。 Vasya 还知道明天将正好有 $n$ 位访客。对于每一位访客，Vasya 都知道他到达护照办公室的时刻。每位访客都会排队，直到被接待员服务完之前不会离开。如果有访客到达时接待员是空闲的（特别是前一位访客刚被服务完且队列为空），接待员会立刻为新到的访客服务。  “接待处1” 对于每个访客，到达护照办公室的时刻都是正整数。Vasya 如果需要，可以在时刻零（即午夜）到达办公室，但他只能在整数的时刻到达。如果 Vasya 跟其他访客同时到达，他必须让所有同时到达的访客先排队，自己排在这些访客的最后。 Vasya 希望选择一个到达时刻，被接待员接待，并且排队的总时间最少。请帮帮他！

第一行包含三个整数：接待员开始工作的时刻 $t_s$，结束工作的时刻 $t_f$，以及接待员为每位访客服务的时间 $t$。 第二行包含一个整数 $n$，表示访客人数（$0 \leq n \leq 100000$）。 第三行包含 $n$ 个正整数，表示每位访客到达护照办公室的时刻，按非递减顺序排列。 所有时刻均以分钟为单位，且不超过 $10^{12}$；保证 $t_s < t_f$。保证 Vasya 可以选择一个到达时刻并被接待员接待。

输出一个非负整数，表示 Vasya 应该到达护照办公室的时刻。如果 Vasya 与其他访客同时到达，他必须站在这些访客的最后。如果有多个答案，输出任意一个即可。

在第一个样例中，第一个访客恰好在接待员开始工作的时刻到达，并且被服务两分钟。午夜后第 12 分钟时，接待员停止服务第一个访客，如果 Vasya 在此时到达，他会立刻被接待，因为下一个访客要到第 13 分钟才到。 在第二个样例中，Vasya 必须比其他人提前到达才能被及时接待。 由 ChatGPT 5 翻译