Problem I
Infinite Race
Every year, there is a marathon in Eindhoven. This year, the organizers have come up with something special, and instead of being over after 42 kilometres, the race goes on forever! To keep the organization simple, the race takes place on a running track at Eindhoven university, and the participants run an infinite number of laps on the track.
Anika is excited to be one of the $N$ participants, numbered from $0$ to $N-1$. She was quick to sign up which means she is participant $0$. She starts right after the finish line with all other participants positioned ahead of her on the track. Anika cannot keep track of how many laps she has run, but she remembers when she overtakes someone or when someone overtakes her. $A$ overtaking $B$ means that $A$ passes $B$ which can happen in the same lap, or $A$ can even be some laps ahead or behind $B$.
What is the minimum number of times she must have crossed the finish line? Nobody moves backwards, and no overtaking happens exactly at the finish line. Furthermore, note that the participants do not necessarily run at a constant speed.
![\includegraphics[width=0.7\textwidth ]{track}](/problems/infiniterace2/file/statement/en/img-0001.png)
Input
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 following $Q$ lines describe the events in the order they occurred during the race. The $i$th line contains an integer $x_ i$.
-
If $x_ i > 0$, it means that Anika overtook participant $x_ i$.
-
If $x_ i < 0$, it means that participant $-x_ i$ overtook Anika.
Output
Output a single integer, the minimum number of times Anika must have crossed the finish line.
Constraints and Scoring
-
$2 \le N \le 200\, 000$.
-
$1 \le Q \le 200\, 000$.
-
$1 \le x_ i \le N-1$ or $-(N-1) \le x_ i \le -1$.
Your solution will be tested on a set of test groups, each worth a number of points. Each test group contains a set of test cases. To get the points for a test group, you need to solve all test cases in the test group.
|
Group |
Score |
Limits |
|
1 |
29 |
$N = 2$ |
|
2 |
34 |
$x_{i} > 0$ for all $i$ (that is, Anika only overtakes) |
|
3 |
22 |
$N,Q\leq 100$ |
|
4 |
15 |
No additional constraints |
Examples
Note that some of the samples are not valid input for all test groups.
In the first sample, there are $N = 4$ participants and $Q = 5$ events. Anika first gets overtaken by $2$, who is now a full lap ahead of her. Then she overtakes $2$ back, followed by overtaking $1$ and then being overtaken by $3$. At this point, Anika can still be on her first lap. Finally, she overtakes $2$ again, and to do so means that she must have crossed the finish line at least once.
In the second sample, there is just one participant other than Anika. Anika overtakes the other participant four times, meaning that Anika must have crossed the finish line at least three times.
| Sample Input 1 | Sample Output 1 |
|---|---|
4 5 -2 2 1 -3 2 |
1 |
| Sample Input 2 | Sample Output 2 |
|---|---|
2 4 1 1 1 1 |
3 |
| Sample Input 3 | Sample Output 3 |
|---|---|
2 5 1 -1 1 -1 -1 |
0 |
| Sample Input 4 | Sample Output 4 |
|---|---|
200000 7 199999 199999 1 199999 55 199999 55 |
3 |
| Sample Input 5 | Sample Output 5 |
|---|---|
3 6 1 2 2 2 1 1 |
3 |
