Longest Consecutive Subsequence

Given an unsorted array of integers, your task is to determine the length of the longest subsequence such that all the elements in the subsequence are consecutive integers. The elements in the subsequence do not need to appear in order in the original array. A subsequence is defined as a set of integers \(a, a+1, a+2, \ldots, a+k\) for some integer \(a\) and non-negative integer \(k\).

Your algorithm should achieve an average time complexity of \(O(n)\), where \(n\) is the number of elements in the array.

inputFormat

The input is read from standard input and consists of two lines:

• The first line contains a single integer \(n\) (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 representing the length of the longest consecutive subsequence.

7
100 4 200 1 3 2 101

4