每年，埃因霍温都会举办一场马拉松比赛。今年，组织者想出了一些特别的点子：比赛不再是在 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 最少必须跨越终点线的次数。

数据范围

• $2 \le N \le 200\,000$
• $1 \le Q \le 200\,000$
• $1 \le x_i \le N - 1$ 或 $-(N - 1) \le x_i \le -1$

子任务

样例

注意，某些样例对于所有子任务来说可能不是有效的输入。

在第一个样例中，有 $N = 4$ 名参赛者和 $Q = 5$ 个事件。Anika 首先被 $2$ 号超越，此时 $2$ 号领先她整整一圈。然后她反超了 $2$ 号，接着超越了 $1$ 号，随后又被 $3$ 号超越。此时，Anika 可能仍处于她的第一圈。最后，她再次超越了 $2$ 号，这意味着她必须至少跨越过一次终点线。

在第二个样例中，除了 Anika 之外只有一名参赛者。Anika 超越了该参赛者四次，这意味着 Anika 必须至少跨越过三次终点线。

样例输入 1

4
5
-2
2
1
-3
2

样例输出 1

1

样例输入 2

2
4
1
1
1
1

样例输出 2

3

样例输入 3

2
5
1
-1
1
-1
-1

样例输出 3

0

样例输入 4

200000
7
199999
199999
1
199999
55
199999
55

样例输出 4

3

样例输入 5

3
6
1
2
2
2
1
1

样例输出 5

3