题目背景

Day 1 Problem A.

题面译自 EGOI2024 infiniterace。翻译来自于 ChatGPT 并进行人工校对，若有误请联系 rui_er。

题目描述

每年在埃因霍温都会举行一场马拉松。今年，组织者们想出了一个特别的点子，比赛不再在 42 公里后结束，而是无限进行下去！为了简化组织工作，比赛在埃因霍温大学的一个跑道上进行，参赛者在跑道上无限循环。

Anika 很高兴成为 $N$ 名参赛者之一，编号从 $0$ 到 $N - 1$。她很快报名，因此她是参赛者 $0$。她在终点线后起跑，其他参赛者都在她前面。Anika 无法记住她跑了多少圈，但她记得何时超越了某人或何时被某人超越。她至少需要多少次越过终点线？没有人会后退，也不会在终点线上发生超车。此外，参赛者的速度不一定是恒定的。

输入格式

输入的第一行包含一个整数 $N$，表示参赛者的数量。

第二行包含一个整数 $Q$，表示事件的数量。

接下来的 $Q$ 行按比赛过程中发生的顺序描述事件。第 $i$ 行包含一个整数 $x_i$。

• 如果 $x_i > 0$，表示 Anika 超越了参赛者 $x_i$。
• 如果 $x_i < 0$，表示参赛者 $-x_i$ 超越了 Anika。

输出格式

输出一个整数，表示 Anika 至少穿过终点线的次数。

4
5
-2
2
1
-3
2

1

2
4
1
1
1
1

3

2
5
1
-1
1
-1
-1

0

200000
7
199999
199999
1
199999
55
199999
55

3

3
6
1
2
2
2
1
1

3

提示

样例解释

在第一个样例中，有 $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 中被放在多个子任务中。为节省评测资源及整理数据的工作量，这些测试点被放在包含它的所有子任务中编号最小的一个。这可能导致一份代码得到比预期更高的分数，但是无法过题。