Longest Consecutive Sequence

Given an unsorted array of integers, find the length of the longest consecutive sequence. A consecutive sequence is defined as a set of numbers where each number is exactly one more than the previous number. Formally, if there exists an integer a such that the array contains a, a+1, a+2, \( \dots \), a+k-1, then the length of this sequence is \(k\). Your algorithm should run in \(O(n)\) time on average.

The input is provided via standard input and the output should be printed to standard output.

inputFormat

The first line contains a non-negative integer n which represents the number of elements in the array. The second line contains n space-separated integers representing the array elements. If n is 0, the array is empty.

outputFormat

Output a single line containing the length of the longest consecutive sequence found in the array.

6
100 4 200 1 3 2

4