무한 달리기

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

요약

원형 트랙에서 Anika와 다른 주자들이 추월한 순서가 주어질 때, Anika가 최소 몇 번 결승선을 통과했어야 하는지 구합니다.

난이도: 보통10점 중 5점
유형: 배열, 시뮬레이션
정답자: 아직 제출이 없습니다

문제

매년 에인트호번에서 마라톤이 열린다. 올해 주최 측은 특별한 아이디어를 내놓았다. 레이스는 42킬로미터에서 끝나지 않고 영원히 계속된다. 운영을 단순하게 하려고 레이스는 에인트호번 대학교의 러닝 트랙에서 열리며, 참가자들은 트랙을 무한히 많이 돈다.

아니카는 번호가 $0$ 부터 $N-1$ 까지인 $N$ 명의 참가자 중 한 명이다. 그녀가 가장 먼저 신청했으므로 참가자 $0$ 번이다. 그녀는 결승선 바로 뒤에서 출발하고, 다른 참가자들은 모두 트랙에서 그녀보다 앞에 있다. 아니카는 자신이 몇 바퀴를 돌았는지 세지 못하지만, 누군가를 추월하거나 누군가에게 추월당한 순간은 기억한다. 아니카가 결승선을 최소 몇 번 통과했어야 하는가? 아무도 뒤로 달리지 않으며, 결승선에서 정확히 추월이 일어나지는 않는다. 또한 참가자들이 항상 일정한 속도로 달리는 것은 아니다.

입력

첫째 줄에 참가자 수 $N$ 이 주어진다.

둘째 줄에 사건의 수 $Q$ 가 주어진다.

이어지는 $Q$ 개의 줄에는 레이스 중 발생한 순서대로 사건이 주어진다. $i$ 번째 줄에는 정수 $x_i$ 가 하나 주어진다.

$x_i > 0$ 이면 아니카가 참가자 $x_i$ 를 추월했다는 뜻이다.
$x_i < 0$ 이면 참가자 $-x_i$ 가 아니카를 추월했다는 뜻이다.

출력

아니카가 결승선을 통과했어야 하는 최소 횟수를 정수 하나로 출력한다.

제한

$2 \le N \le 200\,000$ .
$1 \le Q \le 200\,000$ .
$1 \le x_i \le N-1$ 또는 $-(N-1) \le x_i \le -1$ .

힌트

일부 예제는 모든 테스트 그룹에서 유효한 입력이 아닐 수 있다.

첫 번째 예제에서 참가자는 $N = 4$ 명이고 사건은 $Q = 5$ 개다. 2번 참가자가 먼저 아니카를 추월해서 2번은 그녀보다 정확히 한 바퀴 앞서게 된다. 이어서 아니카가 2번을 다시 추월하고, 1번을 추월한 뒤, 3번에게 추월당한다. 이 시점까지는 아니카가 여전히 첫 바퀴를 돌고 있을 수 있다. 마지막으로 아니카가 2번을 다시 추월하는데, 이를 위해서는 결승선을 최소 한 번은 통과했어야 한다.

두 번째 예제에서는 아니카 외의 참가자가 한 명뿐이다. 아니카가 그 참가자를 네 번 추월하므로, 아니카는 결승선을 최소 세 번 통과했어야 한다.

예제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
```