Infinite Race

시간 제한1초메모리 제한1024 MB

요약

원형 트랙에서 0번 주자가 다른 주자와 주고받은 추월 사건 순서가 주어질 때, 0번 주자가 결승선을 통과한 최소 횟수를 구한다.

난이도: 보통10점 중 7점
유형: 그리디, 수학, 구현, 시뮬레이션
정답자: 아직 제출이 없습니다

문제

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.

입력

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.

제한

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

힌트

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.

예제5

예제 1
입력
```
4
5
-2
2
1
-3
2
```
예상 출력
```
1
```
예제 2
입력
```
2
4
1
1
1
1
```
예상 출력
```
3
```
예제 3
입력
```
2
5
1
-1
1
-1
-1
```
예상 출력
```
0
```

예제 4

입력

예상 출력

예제 5
입력
```
3
6
1
2
2
2
1
1
```
예상 출력
```
3
```