infiniterace — EGOI contest
Task type: batch | Time limit: 1 s | Memory limit: 1024 MB | Difficulty: 14
Algorithms: ad-hoc, greedy, data structures, hash map

![XEGOI](_page_0_Picture_0.jpeg)

# A. Infinite Race

| Problem Name | Infinite Race |
|---|---|
| Time Limit | 1 seconds |
| Memory Limit | 1 gigabyte |

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. 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.

![Track](_page_0_Picture_6.jpeg)

### 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<sub>i</sub>*.

*   If *x<sub>i</sub>* > 0, it means that Anika overtook participant *x<sub>i</sub>*.
*   If *x<sub>i</sub>* < 0, it means that participant −*x<sub>i</sub>* overtook Anika.

### Output

Output a single integer, the minimum number of times Anika must have crossed the finish line.

## Constraints and Scoring

*   2 ≤ *N* ≤ 200 000.
*   1 ≤ *Q* ≤ 200 000.
*   1 ≤ *x<sub>i</sub>* ≤ *N* − 1 or −(*N* − 1) ≤ *x<sub>i</sub>* ≤ −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<sub>i</sub>* > 0 for all *i* (that is, Anika only overtakes) |
| 3 | 22 | *N*, *Q* ≤ 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.

| Input | Output |
|---|---|
| 4<br>5<br>-2<br>2<br>1<br>-3<br>2 | 1 |
| 2<br>4<br>1<br>1<br>1<br>1 | 3 |
| 2<br>5<br>1<br>-1<br>1<br>-1<br>-1 | 0 |
| 200000<br>7<br>199999<br>199999<br>1<br>199999<br>55<br>199999<br>55 | 3 |
| 3<br>6<br>1<br>2<br>2<br>2<br>1<br>1 | 3 |

Starter code: