| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 9 | 5 | 5 | 62.500% |
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$.
Output a single integer, the minimum number of times Anika must have crossed the finish line.
| 번호 | 배점 | 제한 |
|---|---|---|
| 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 |
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
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.