Challenge: Longest Run of Consecutive Numbers

Lab C++ Intermediate 20 points

Read n 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) with unordered_set – no sorting.

Input

Line 1: n. Line 2: n whole numbers.

Output

One number.

Example

Input

6
100 4 200 1 3 2

Output

Sample input available Sample output available

Editor

C++

Hints

Put all numbers in an unordered_set.

Only count from x when x - 1 is NOT in the set.

Then count up while x + len is in the set.

Solution explanation

Each run is counted once from its smallest number: O(n) overall.

Show solution

#include <algorithm>
#include <iostream>
#include <unordered_set>
using namespace std;

int main() {
    int n;
    cin >> n;
    unordered_set<int> s;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        s.insert(x);
    }
    int best = 0;
    for (int x : s) {
        if (!s.count(x - 1)) {               // x starts a run
            int len = 1;
            while (s.count(x + len)) len++;
            best = max(best, len);
        }
    }
    cout << best << endl;
    return 0;
}

Output

Answer