[EGOI 2024] Infinite Race / 无限赛跑

每年在埃因霍温都会举行一场马拉松。今年，组织者们想出了一个特别的点子，比赛不再在 42 公里后结束，而是无限进行下去！为了简化组织工作，比赛在埃因霍温大学的一个跑道上进行，参赛者在跑道上无限循环。 Anika 很高兴成为 $N$ 名参赛者之一，编号从 $0$ 到 $N - 1$。她很快报名，因此她是参赛者 $0$。她在终点线后起跑，其他参赛者都在她前面。Anika 无法记住她跑了多少圈，但她记得何时超越了某人或何时被某人超越。她至少需要多少次越过终点线？没有人会后退，也不会在终点线上发生超车。此外，参赛者的速度不一定是恒定的。  ## Input 输入的第一行包含一个整数 $N$，表示参赛者的数量。 第二行包含一个整数 $Q$，表示事件的数量。 接下来的 $Q$ 行按比赛过程中发生的顺序描述事件。第 $i$ 行包含一个整数 $x_i$。 - 如果 $x_i > 0$，表示 Anika 超越了参赛者 $x_i$。 - 如果 $x_i < 0$，表示参赛者 $-x_i$ 超越了 Anika。 ## Output 输出一个整数，表示 Anika 至少穿过终点线的次数。 [samples] ## Background Day 1 Problem A. 题面译自 [EGOI2024 infiniterace](https://wiki.egoi2024.nl/tasks/infiniterace/statement-isc.pdf)。翻译来自于 [ChatGPT](https://chatgpt.com/) 并进行人工校对，若有误请联系 [rui_er](https://www.luogu.com.cn/user/122461)。 ## Note **样例解释** 在第一个样例中，有 $N = 4$ 名参赛者和 $Q = 5$ 个事件。Anika 首先被参赛者 $2$ 超越，后者现在比她快一整圈。然后她反超 $2$，接着超越 $1$，随后被 $3$ 超越。在此时，Anika 仍然可以在她的第一圈。最后，她再次超越 $2$，为了实现这一点，意味着她至少穿过了终点线一次。 在第二个样例中，除了 Anika 之外只有一个参赛者。Anika 四次超越了另一个参赛者，这意味着 Anika 至少穿过终点线三次。 --- **数据范围** 对于全部数据，$2 \le N \le 2\times 10^5$，$1 \le Q \le 2\times 10^5$，$1 \le x \le N - 1$ 或 $-(N - 1) \le x \le -1$。 - 子任务一（$29$ 分）：$N=2$。 - 子任务二（$34$ 分）：$x_i > 0$。 - 子任务三（$22$ 分）：$N,Q\le 100$。 - 子任务四（$15$ 分）：无特殊限制。 注：部分测试点在 EGOI 中被放在多个子任务中。为节省评测资源及整理数据的工作量，这些测试点被放在包含它的所有子任务中编号最小的一个。这可能导致一份代码得到比预期更高的分数，但是无法过题。