Longest Consecutive Sequence

Given an unsorted array of integers, your task is to find the length of the longest consecutive elements sequence. A consecutive sequence is defined as a set of numbers in the form \(a, a+1, a+2, \ldots, a+k\) that appear in the array, not necessarily in order. For example, in the array [100, 4, 200, 1, 3, 2], the longest consecutive sequence is [1, 2, 3, 4] with a length of 4.

Your algorithm should ideally run in \(O(n)\) time complexity.

inputFormat

The input is given via standard input (stdin). The first line contains an integer \(n\) representing the number of elements in the array. The second line contains \(n\) space-separated integers.

outputFormat

Output a single integer to standard output (stdout) which represents the length of the longest consecutive elements sequence.

6
100 4 200 1 3 2

4