Longest Consecutive Sequence

Given an unsorted list of integers, the task is to find the length of the longest subsequence of consecutive integers. Two integers are considered consecutive if their difference is exactly one. The subsequence does not have to appear contiguously in the list.

For example, in the list [100, 4, 200, 1, 3, 2], the longest consecutive subsequence is [1, 2, 3, 4], whose length is 4.

This problem may include negative numbers and duplicate values. Formally, if the input array is \(A = [a_1,a_2,\dots,a_n]\), you are to find the maximum integer \(L\) such that there exists a set \( \{x, x+1, \dots, x+L-1\}\) where each element is found in \(A\).

inputFormat

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

outputFormat

Output a single integer to standard output (stdout) representing the length of the longest consecutive subsequence found within the array.

6
100 4 200 1 3 2

4