An airfield's runway is lined with edge lights installed at every integer meter mark from lower to upper, inclusive. After a storm, a maintenance crew walks the strip and logs the exact meter positions where the light is confirmed to still be working, given in strictly increasing order. Every position they didn't note down is dark. Report every maximal contiguous stretch of dark positions, in increasing order of where it starts.
A single line containing three integers lower, upper, and n, followed by n integers giving the positions of the working lights in strictly increasing order. Every working-light position lies in [lower, upper].
Print an integer k, the number of dark stretches. Then print k lines, each with two integers start end: the inclusive bounds of one maximal dark stretch, ordered by increasing start. A stretch that is a single dark position is printed as start start.
n working-light positions are strictly increasing, and each lies in [lower, upper].Example 1
Input
0 99 5 0 1 3 50 75
Expected
4 2 2 4 49 51 74 76 99
Explanation
Positions 0, 1, 3, 50, and 75 are confirmed working within [0, 99]. Position 2 is dark on its own (2 2). Positions 4 through 49 are one dark stretch (4 49). Positions 51 through 74 are one dark stretch (51 74). Positions 76 through 99 are one dark stretch (76 99). That gives 4 stretches total.
Example 2
Input
1 1 0
Expected
1 1 1
Explanation
The range is just the single position 1, and no working light was logged at all, so the entire range [1, 1] is one dark stretch, printed as 1 1.
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 →