Longest Consecutive Sequence

Given an unsorted array of integers, find the length of the longest sequence of consecutive integers. Two numbers are consecutive if they differ by exactly 1. The solution should run in O(n) time complexity.

Note: The consecutive sequence does not need to be in order in the input array.

For example, given the array [100, 4, 200, 1, 3, 2], the longest consecutive sequence is [1, 2, 3, 4], so the answer is 4.

The key observation is that if an element num is the start of a sequence (i.e. num - 1 is not present in the array), then the sequence can be built by checking for num + 1, num + 2, \ldots. Formally, if we let \( S \) be the set of numbers, then for an element \( num \) that satisfies \[ num - 1 \notin S, \] the length of the consecutive sequence starting at \( num \) is calculated by finding the maximum \( k \) such that \[ num,\, num+1,\, \ldots,\, num+k-1 \in S. \]

inputFormat

The first line contains an integer \( n \), the number of elements in the array. If \( n \gt 0 \), the second line contains \( n \) space-separated integers.

outputFormat

Output a single integer representing the length of the longest consecutive sequence.

## sample

6
100 4 200 1 3 2

4

</p>