Problem Description

Every year, a marathon is held in Eindhoven. This year, the organizers came up with a special idea: the race no longer ends after 42 kilometers but continues indefinitely! To simplify the organization, the race takes place on a track at Eindhoven University, where participants run in an infinite loop.

Anika is delighted to be one of the $N$ participants, numbered from $0$ to $N - 1$. She signed up quickly, so she is participant $0$. She starts behind the finish line, with all other participants ahead of her. Anika cannot remember how many laps she has run, but she remembers when she overtook someone or when someone overtook her. How many times does she need to cross the finish line at least? No one will go backward, and no overtaking will occur at the finish line. Additionally, participants' speeds are not necessarily constant.

Input Format

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 next $Q$ lines describe the events in the order they occur during the race. The $i$-th line contains an integer $x_i$.

• If $x_i > 0$, it means Anika overtook participant $x_i$.
• If $x_i < 0$, it means participant $-x_i$ overtook Anika.

Output Format

Output a single integer, the minimum number of times Anika crosses the finish line.

Sample Input and Output

Sample Input #1

4
5
-2
2
1
-3
2

Sample Output #1

1

Sample Input #2

2
4
1
1
1
1

Sample Output #2

3

Sample Input #3

2
5
1
-1
1
-1
-1

Sample Output #3

0

Sample Input #4

200000
7
199999
199999
1
199999
55
199999
55

Sample Output #4

3

Sample Input #5

3
6
1
2
2
2
1
1

Sample Output #5

3

Notes

Sample Explanation

In the first sample, there are $N = 4$ participants and $Q = 5$ events. Anika is first overtaken by participant $2$, who is now a full lap ahead of her. Then she overtakes $2$, then $1$, and is then overtaken by $3$. At this point, Anika can still be on her first lap. Finally, she overtakes $2$ again, which means she must have crossed the finish line at least once.

In the second sample, there is only one other participant besides Anika. Anika overtakes the other participant four times, which means Anika must have crossed the finish line at least three times.

Data Range

For all data, $2 \le N \le 2 \times 10^5$, $1 \le Q \le 2 \times 10^5$, $1 \le x \le N - 1$ or $-(N - 1) \le x \le -1$.

• Subtask 1 (29 points): $N = 2$.
• Subtask 2 (34 points): $x_i > 0$.
• Subtask 3 (22 points): $N, Q \le 100$.
• Subtask 4 (15 points): No additional constraints.

Note: Some test cases are included in multiple subtasks during EGOI. To save evaluation resources and simplify data management, these test cases are included in the subtask with the smallest number that contains them. This may result in a higher score than expected for a submission, but it will not allow passing the problem.

见题面 Input 部分

见题面 Output 部分