Attendance gives you the roll numbers of the students present, in no particular order and possibly with repeats. Find the length of the longest run of consecutive integers that are all present (for example 7, 8, 9, 10). Aim for linear time — sorting is the slower, simpler answer.
Constraints
- 1 ≤ n ≤ 100000
- −10^9 ≤ value ≤ 10^9
Input and output
- Input
- Line 1: n. Line 2: n integers.
- Output
- One integer.
Examples
Input 1
6
100 4 200 1 3 2Output
4Roll numbers 1, 2, 3, 4 are all present: a run of 4.
Input 2
4
5 5 6 6Output
2Duplicates do not extend a run: 5, 6 gives 2.
Show hints
- Put every number in a hash set.
- Only start counting from a number x whose predecessor x − 1 is missing.
Show the explanation
Put all numbers in a hash set. A number x starts a run only if x − 1 is not in the set. From each such start, count upward while x + 1, x + 2, … are present. Every number is visited at most twice (once in the outer loop, once while extending the run that contains it), so the total is O(n) expected. Sorting and scanning gives O(n log n) and is a fine first answer.
Original UniCircle question. Last reviewed 22 Oct 2026.