레이팅 미적용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.
(An illustrative figure from the official statement is omitted here.)
- \(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
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 a single integer, the minimum number of times Anika must have crossed the finish line.
| 서브태스크 | 점수 | 설명 |
|---|---|---|
Subtask 1 | 29점 | None |
Subtask 2 | 34점 | None |
Subtask 3 | 22점 | None |
Subtask 4 | 15점 | None |
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