An audio archive assigns every vinyl record on its shelves a unique positive integer shelf code. When all the codes on the shelves are sorted from smallest to largest, the archivist calls the initial stretch of codes a continuous run if, starting from the very smallest code, each following code in that stretch is exactly one greater than the code before it. A run consisting of just the smallest code by itself is always considered continuous (trivially, a run of length 1 has nothing to compare against).
Given the full collection of shelf codes, find the longest continuous run starting from the smallest code, add up the codes inside that run to get a value S, and then report the smallest positive integer strictly greater than S that is not already in use as a shelf code — that is the next code the archivist can safely stamp onto an incoming record without colliding with anything already on the shelves.
Line 1: a single integer n, the number of shelf codes. Line 2: n space-separated positive integers, the shelf codes (all pairwise distinct), in no particular order.
A single line containing one integer: the smallest positive integer strictly greater than S that does not appear among the given shelf codes.
1 <= n <= 10^5 1 <= each shelf code <= 10^9 All shelf codes are pairwise distinct.
Example 1
Input
5 7 8 3 4 5
Expected
13
Explanation
Sorted codes are 3, 4, 5, 7, 8. Starting from the smallest (3), the run 3, 4, 5 is continuous (each is one more than the last), but 7 breaks it. The run sum is S = 3+4+5 = 12. Checking integers above 12: 13 is not used as a code, so 13 is printed.
Example 2
Input
5 1 2 3 4 100
Expected
11
Explanation
Sorted codes are 1, 2, 3, 4, 100. The run 1, 2, 3, 4 is continuous and stops before 100. The run sum is S = 1+2+3+4 = 10. 11 is not among the codes, so 11 is printed.
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 →