Challenge: Longest Run of Consecutive Numbers

Lab Python Intermediate 20 points

Read a list of numbers in any order. Print the length of the longest run of consecutive whole numbers that can be made from them (like 1, 2, 3, 4). Aim for O(n) using a set – no sorting.

Input

One line of whole numbers.

Output

One number.

Example

Input

100 4 200 1 3 2

Output

Sample input available Sample output available

Editor

Python

Hints

Put all numbers in a set.

Only start counting from x when x - 1 is NOT in the set – that's the start of a run.

Then count up while x + 1, x + 2, ... are in the set.

Solution explanation

Each run is counted once, starting from its smallest number, so the total work is O(n).

Show solution

nums = set(map(int, input().split()))
best = 0
for x in nums:
    if x - 1 not in nums:
        length = 1
        while x + length in nums:
            length += 1
        best = max(best, length)
print(best)

Output

Answer