A harbor channel has n buoys arranged in a circle and numbered 1 through n in clockwise order (buoy n sits immediately clockwise-adjacent to buoy 1). A rotating lighthouse beam starts resting on some buoy, illuminating it once. The beam then performs m sweep passes, one after another; during each pass the beam rotates strictly clockwise, illuminating every buoy it newly reaches — one at a time, in increasing numeric order and wrapping from buoy n back to buoy 1 — until it comes to rest on that pass's logged buoy (which is illuminated as the final step of the pass, and only that final buoy and every buoy strictly in between the pass's start and end are newly illuminated; the buoy the beam started the pass on is not illuminated again, since it was already counted). A logbook records the buoy the beam rests on before the first pass, and the buoy it rests on at the end of each of the m passes. If a pass's logged buoy is the same as where the beam already rested, that pass illuminates nothing new. After all m passes, determine which buoy or buoys were illuminated the greatest total number of times, and report them in ascending numeric order.
Line 1: two integers n and m. Line 2: m + 1 integers log[0], log[1], ..., log[m] (each between 1 and n) — log[0] is the buoy the beam rests on before the first pass, and log[i] for i >= 1 is the buoy the beam rests on at the end of the i-th pass.
Print the buoy numbers that achieve the maximum illumination count, in ascending order, space-separated on a single line.
Example 1
Input
4 3 1 3 1 2
Expected
1 2
Explanation
The beam starts resting on buoy 1 (1 illumination so far). Pass 1 goes from buoy 1 to buoy 3, newly illuminating buoys 2 and 3. Pass 2 goes from buoy 3 to buoy 1, wrapping through buoy 4, newly illuminating buoys 4 and 1 (buoy 1's second illumination). Pass 3 goes from buoy 1 to buoy 2, newly illuminating buoy 2 (its second illumination). Final counts: buoy 1 = 2, buoy 2 = 2, buoy 3 = 1, buoy 4 = 1. Buoys 1 and 2 are tied for the most illuminations, so the answer is "1 2".
Example 2
Input
2 5 2 1 2 1 2 1
Expected
1 2
Explanation
With only two buoys, the beam starts on buoy 2 (1 illumination) and then alternates buoys every pass: 2 to 1, 1 to 2, 2 to 1, 1 to 2, 2 to 1 — each pass newly illuminating whichever buoy it lands on. Counting the initial rest plus the five passes, buoy 1 ends up illuminated 3 times and buoy 2 ends up illuminated 3 times, so both are equally the busiest and the answer is "1 2".
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →