Longest Consecutive Sequence

Given an unsorted array of integers, your task is to determine the length of the longest consecutive elements sequence.

For example, if the input array is [100, 4, 200, 1, 3, 2], the longest consecutive sequence is [1, 2, 3, 4] with a length of 4.

The consecutive sequence means a set of numbers where each element differs from its previous element by exactly 1. Formally, a sequence starting with \(a\) can be represented as \(a,\,a+1,\,a+2,\,\dots,\,a+k\) for some \(k\geq 0\).

Your solution should aim for an efficient implementation. In particular, an \(O(n)\) approach using a hash set is recommended.

inputFormat

The first line of input 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 representing the length of the longest consecutive elements sequence.

6
100 4 200 1 3 2

4