Background

Day 1 Problem A.

This statement is translated from EGOI2024 infiniterace. The translation comes from ChatGPT and has been proofread manually. If there are any mistakes, please contact rui_er.

Problem Description

Every year, a marathon is held in Eindhoven. This year, the organizers came up with a special idea: the race will no longer end after 42 kilometers, but will continue forever. To simplify the organization, the race takes place on a track at Eindhoven University, and the participants run around the track in an infinite loop.

Anika is happy to be one of the $N$ participants, numbered from $0$ to $N - 1$. She registered early, so she is participant $0$. She starts just after the finish line, and all other participants are in front of her. Anika cannot remember how many laps she has run, but she remembers when she overtook someone or when someone overtook her. What is the minimum number of times she must have crossed the finish line? Nobody ever runs backwards, and no overtaking happens on the finish line. Also, the participants' speeds do not have to be constant.

Input Format

The first line of input contains an integer $N$, the number of participants.

The second line contains an integer $Q$, the number of events.

The next $Q$ lines describe the events in the order they happen during the race. The $i$-th line contains an integer $x_i$.

• If $x_i > 0$, it means Anika overtook participant $x_i$.
• If $x_i < 0$, it means participant $-x_i$ overtook Anika.

Output Format

Print one integer: the minimum number of times Anika has crossed the finish line.

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

Hint

Sample Explanation

In the first sample, there are $N = 4$ participants and $Q = 5$ events. Anika is first overtaken by participant $2$, who is now one full lap ahead of her. Then she overtakes $2$ back, then overtakes $1$, and then is overtaken by $3$. At this point, Anika can still be on her first lap. Finally, she overtakes $2$ again. For this to be possible, it means she must have crossed the finish line at least once.

In the second sample, there is only one participant besides Anika. Anika overtakes the other participant four times, which means Anika must have crossed the finish line at least three times.

Constraints

For all testdata, $2 \le N \le 2\times 10^5$, $1 \le Q \le 2\times 10^5$, $1 \le x \le N - 1$ or $-(N - 1) \le x \le -1$.

• Subtask 1 ($29$ points): $N = 2$.
• Subtask 2 ($34$ points): $x_i > 0$.
• Subtask 3 ($22$ points): $N, Q \le 100$.
• Subtask 4 ($15$ points): no special constraints.

Note: Some test points in EGOI are placed in multiple subtasks. To save judging resources and the work of organizing the data, these test points are placed in the subtask with the smallest index among all subtasks that contain them. This may cause a solution to get a higher score than expected, but still not be able to pass the full problem.

Translated by ChatGPT 5