Given an array of positive integers. Find the length of the longest sub-sequence such that elements in the subsequence are consecutive integers, the consecutive numbers can be in any order.
 
Example 1:
Input:
N = 7
a[] = {2,6,1,9,4,5,3}
Output:
6
Explanation:
The consecutive numbers here
are 1, 2, 3, 4, 5, 6. These 6 
numbers form the longest consecutive
subsquence.
Example 2:
Input:
N = 7
a[] = {1,9,3,10,4,20,2}
Output:
4
Explanation:
1, 2, 3, 4 is the longest
consecutive subsequence.
Your Task:
You don't need to read input or print anything. Your task is to complete the function findLongestConseqSubseq() which takes the array arr[] and the size of the array as inputs and returns the length of the longest subsequence of consecutive integers. 
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(N).
Constraints:
1 <= N <= 10^{5}
0 <= a[i] <= 10^{5}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: String algorithms

Data structures

Starter code:  #User function Template for python3

 

class Solution:

    

    # arr[] : the input array

    # N : size of the array arr[]

    

    #Function to return length of longest subsequence of consecutive integers.

    def findLongestConseqSubseq(self,arr, N):

        #code here

Solutions:
class Solution:

	def findLongestConseqSubseq(self, arr, N):
		num_set = set(arr)
		max_len = 0
		for num in num_set:
			if num - 1 not in num_set:
				curr_num = num
				curr_len = 1
				while curr_num + 1 in num_set:
					curr_num += 1
					curr_len += 1
				max_len = max(max_len, curr_len)
		return max_len


class Solution:

	def findLongestConseqSubseq(self, arr, N):
		arr.sort()
		ans = 1
		count = 1
		for i in range(1, N):
			if arr[i - 1] == arr[i]:
				pass
			elif arr[i - 1] + 1 == arr[i]:
				count += 1
			else:
				if count > ans:
					ans = count
				count = 1
		if count > ans:
			ans = count
		return ans


class Solution:

	def findLongestConseqSubseq(self, arr, n):
		ans = 0
		count = 0
		arr.sort()
		v = []
		v.append(arr[0])
		for i in range(1, n):
			if arr[i] != arr[i - 1]:
				v.append(arr[i])
		for i in range(len(v)):
			if i > 0 and v[i] == v[i - 1] + 1:
				count += 1
			else:
				count = 1
			ans = max(ans, count)
		return ans


class Solution:

	def findLongestConseqSubseq(self, arr, N):
		d = {}
		ans = 1
		for i in arr:
			d[i] = True
		for i in arr:
			if d[i]:
				l = []
				l.append(i)
				left = i - 1
				while left in d:
					d[left] = False
					l.append(left)
					left -= 1
				right = i + 1
				while right in d:
					d[right] = False
					l.append(right)
					right += 1
				ans = max(ans, len(l))
		return ans


class Solution:

	def findLongestConseqSubseq(self, arr, N):
		consecutive_nums = 0
		nums = set(arr)
		for num in nums:
			count = 1
			if num - 1 in nums:
				continue
			while num + 1 in nums:
				count += 1
				num += 1
			consecutive_nums = max(consecutive_nums, count)
		return consecutive_nums


class Solution:

	def findLongestConseqSubseq(self, arr, N):
		s = set()
		for i in arr:
			s.add(i)
		ans = 0
		for i in arr:
			if i - 1 not in s:
				j = i
				while j in s:
					j += 1
				ans = max(ans, j - i)
		return ans


class Solution:

	def findLongestConseqSubseq(self, arr, N):
		hashset = set()
		for i in arr:
			hashset.add(i)
		longest_streak = 0
		for i in arr:
			if i - 1 not in hashset:
				currentNum = i
				currentStreak = 1
				while currentNum + 1 in hashset:
					currentNum += 1
					currentStreak += 1
				longest_streak = max(longest_streak, currentStreak)
		return longest_streak


class Solution:

	def findLongestConseqSubseq(self, arr, N):
		if not arr:
			return 0
		arr.sort()
		longest = 1
		prev = arr[0]
		cur = 1
		for i in range(1, N):
			if arr[i] == prev + 1:
				cur += 1
			elif arr[i] != prev:
				cur = 1
			prev = arr[i]
			longest = max(longest, cur)
		return longest


class Solution:

	def findLongestConseqSubseq(self, arr, N):
		nums = [0] * 100001
		(smallest, largest) = (999999, 0)
		for i in arr:
			nums[i] = i
			smallest = min(smallest, i)
			largest = max(largest, i)
		longest = 1
		i = smallest
		while i <= largest:
			if nums[i + 1] == nums[i] + 1:
				tmpLongest = 1
				while nums[i + 1] == nums[i] + 1:
					(tmpLongest, i) = (tmpLongest + 1, i + 1)
				longest = max(longest, tmpLongest)
			i += 1
		return longest


class Solution:

	def findLongestConseqSubseq(self, arr, N):
		s = set()
		for i in arr:
			s.add(i)
		z = []
		c = 0
		maxi = 0
		for i in arr:
			if i - 1 not in s:
				c = 0
				k = i
				while k in s:
					c = c + 1
					maxi = max(c, maxi)
					k = k + 1
		return maxi


class Solution:

	def findLongestConseqSubseq(self, arr, N):
		arr = list(set(arr))
		arr = sorted(arr)
		c = 1
		m = 0
		for i in range(0, len(arr) - 1):
			if arr[i] + 1 == arr[i + 1]:
				c += 1
			else:
				m = max(c, m)
				c = 1
		m = max(c, m)
		return m


class Solution:

	def findLongestConseqSubseq(self, arr, N):
		arr = set(arr)
		arr = list(arr)
		arr.sort()
		mini = min(arr)
		count = 0
		count1 = 0
		max = -1
		for i in range(0, len(arr)):
			if arr[i] == mini:
				count += 1
				mini += 1
			else:
				mini = arr[i]
				mini += 1
				if count > count1:
					count1 = count
					max = count
				count = 1
		if count > count1:
			count1 = count
			max = count
		if max == -1:
			return count
		else:
			return max


class Solution:

	def findLongestConseqSubseq(self, arr, N):
		arr.sort()
		a = []
		id = 0
		b = []
		for i in range(N - 1):
			if arr[i + 1] - arr[i] == 1:
				id = id + 1
			elif arr[i + 1] == arr[i]:
				id = id
			else:
				id = 0
			b.append(id)
		if len(b) == 0:
			ans = 0
		else:
			ans = max(b)
		return ans + 1


class Solution:

	def findLongestConseqSubseq(self, arr, N):
		numSet = set(arr)
		longest = 0
		for i in range(N):
			if arr[i] - 1 not in numSet:
				maxl = 0
				while arr[i] + maxl in numSet:
					maxl += 1
				longest = max(longest, maxl)
		return longest


class Solution:

	def findLongestConseqSubseq(self, arr, N):
		arr = list(set(arr))
		arr.sort()
		maxLen = 1
		count = 1
		for i in range(len(arr) - 1):
			if arr[i] + 1 == arr[i + 1]:
				count += 1
			else:
				count = 1
			maxLen = max(maxLen, count)
		return maxLen


class Solution:

	def findLongestConseqSubseq(self, arr, n):
		s = set()
		ans = 0
		for ele in arr:
			s.add(ele)
		for i in range(n):
			if arr[i] - 1 not in s:
				j = arr[i]
				while j in s:
					j += 1
				ans = max(ans, j - arr[i])
		return ans


class Solution:

	def findLongestConseqSubseq(self, arr, N):
		visit = [0] * (max(arr) + 1)
		for i in range(N):
			visit[arr[i]] = 1
		max_len = 0
		le = 0
		for i in range(max(arr) + 1):
			if visit[i] == 1:
				le += 1
				max_len = max(max_len, le)
			else:
				le = 0
		return max_len


class Solution:

	def findLongestConseqSubseq(self, arr, N):
		arr = set(arr)
		x = min(arr)
		y = max(arr)
		cur = 0
		ans = 1
		while x <= y:
			if x in arr:
				cur += 1
			else:
				cur = 0
			x += 1
			ans = max(ans, cur)
		return ans


class Solution:

	def findLongestConseqSubseq(self, arr, N):
		d = {}
		max_ = 1
		for i in arr:
			d[i] = 1
		for k in d.keys():
			if k - 1 in d.keys():
				continue
			else:
				count = 1
				x = k
				while x + 1 in d.keys():
					count += 1
					x += 1
				if count > max_:
					max_ = count
		return max_


class Solution:

	def findLongestConseqSubseq(self, arr, N):
		new = set(arr)
		longest = 0
		for i in range(N):
			if arr[i] - 1 not in new:
				value = arr[i]
				maxlength = 0
				while arr[i] + maxlength in new:
					maxlength += 1
				longest = max(longest, maxlength)
		return longest


class Solution:

	def findLongestConseqSubseq(self, arr, N):
		l = 0
		max_l = 0
		set_a = set(arr)
		len_s = len(set_a)
		list_a = list(set_a)
		list_a.sort()
		for i in range(len_s - 1):
			if list_a[i] + 1 == list_a[i + 1]:
				l += 1
				if l > max_l:
					max_l = l
			else:
				l = 0
		return max_l + 1


class Solution:

	def findLongestConseqSubseq(self, arr, N):
		longg = 0
		longest = 0
		de = set(arr)
		for n in arr:
			if n - 1 not in de:
				longg = 0
				while n + longg in de:
					longg += 1
				longest = max(longg, longest)
		return longest


class Solution:

	def findLongestConseqSubseq(self, arr, N):
		arr.sort()
		c = 1
		lc = 1
		for i in range(1, N):
			if arr[i] == arr[i - 1] + 1:
				c += 1
				lc = max(c, lc)
			elif arr[i] != arr[i - 1]:
				c = 1
		return lc


class Solution:

	def findLongestConseqSubseq(self, arr, N):
		subseq = []
		maxLen = 0
		sortedseq = sorted(arr)
		for x in sortedseq:
			if len(subseq) == 0:
				subseq = [x]
				maxLen = 1
			elif x - subseq[-1] == 1:
				subseq.append(x)
			elif x == subseq[-1]:
				continue
			else:
				maxLen = max(len(subseq), maxLen)
				subseq = [x]
		maxLen = max(len(subseq), maxLen)
		return maxLen


class Solution:

	def findLongestConseqSubseq(self, arr, N):
		arr.sort()
		maxi = 0
		count = 1
		if N == 1:
			return N
		for i in range(N - 1):
			if arr[i + 1] == arr[i]:
				count += 1
				maxi = max(count, maxi)
			if arr[i + 1] == arr[i] + 1:
				count += 1
				maxi = max(count, maxi)
			else:
				count = 1
				maxi = max(count, maxi)
		return maxi


class Solution:

	def findLongestConseqSubseq(self, arr, n):
		a.sort()
		t = 1
		c = 1
		for i in range(1, n):
			if arr[i] - arr[i - 1] == 1:
				c += 1
			elif arr[i] - arr[i - 1] != 0:
				t = max(t, c)
				c = 1
		return max(t, c)


class Solution:

	def findLongestConseqSubseq(self, arr, N):
		sn = set(arr)
		longest = 1
		max = 0
		for s in sn:
			if s - 1 in sn:
				continue
			else:
				c = s + 1
				while c in sn:
					c += 1
					longest += 1
				if longest > max:
					max = longest
				longest = 1
		return max


class Solution:

	def findLongestConseqSubseq(self, arr, N):
		arr.sort()
		curr = arr[0]
		curr_sum = 1
		max_ele = 1
		for i in range(1, N):
			if arr[i] - curr == 1:
				curr = a[i]
				curr_sum += 1
			elif arr[i] == curr:
				continue
			else:
				curr = a[i]
				curr_sum = 1
			max_ele = max(max_ele, curr_sum)
		return max_ele


class Solution:

	def findLongestConseqSubseq(self, arr, n):
		numset = set(arr)
		mx = 0
		for i in numset:
			if i - 1 not in numset:
				curr_num = i
				curr_len = 1
				while curr_num + 1 in numset:
					curr_num += 1
					curr_len += 1
				if curr_len > mx:
					mx = curr_len
		return mx


class Solution:

	def findLongestConseqSubseq(self, arr, N):
		array = list(set(arr))
		array.sort()
		(result, count) = (0, 0)
		n = len(array)
		i = 0
		while i < n:
			j = i
			count = 1
			while j < n - 1 and array[j] + 1 == array[j + 1]:
				count += 1
				j += 1
			result = max(result, count)
			i = j + 1
		return result


class Solution:

	def findLongestConseqSubseq(self, nums, n):
		if not nums:
			return 0
		nums.sort()
		ans = 1
		prev = nums[0]
		count = 1
		for i in range(n):
			if nums[i] == prev + 1:
				count += 1
			elif nums[i] != prev:
				count = 1
			prev = nums[i]
			ans = max(ans, count)
		return ans


class Solution:

	def findLongestConseqSubseq(self, arr, N):
		arr.sort()
		ans = 1
		curr = 1
		last = arr[0]
		i = 1
		while i < N:
			if arr[i] == last:
				i += 1
			elif arr[i] - 1 == last:
				curr += 1
				last = arr[i]
				i += 1
			else:
				ans = max(ans, curr)
				curr = 1
				last = arr[i]
				i += 1
		return max(ans, curr)


class Solution:

	def findLongestConseqSubseq(self, arr, N):
		arr.sort()
		v = set()
		ans = 0
		for i in arr:
			v.add(i)
		for i in range(N):
			if arr[i] - 1 not in v:
				j = arr[i]
				while j in v:
					j = j + 1
				ans = max(ans, j - arr[i])
		return ans


class Solution:

	def findLongestConseqSubseq(self, arr, N):
		S = set(arr)
		ans = 0
		for x in arr:
			if x - 1 not in S:
				y = x + 1
				while y in S:
					y += 1
				ans = max(ans, y - x)
		return ans


class Solution:

	def findLongestConseqSubseq(self, arr, n):
		arr.sort()
		c = 1
		ans = 1
		x = arr[0]
		for i in range(1, n):
			if x + 1 == arr[i]:
				c += 1
				x = arr[i]
				ans = max(ans, c)
			elif x == arr[i]:
				continue
			else:
				ans = max(ans, c)
				x = arr[i]
				c = 1
		return ans


class Solution:

	def findLongestConseqSubseq(self, arr, N):
		arr = sorted(arr)
		maxSeq = 0
		currSeq = 0
		for i in range(N):
			if i != 0 and arr[i] == arr[i - 1]:
				continue
			elif i == 0 or arr[i] == arr[i - 1] + 1:
				currSeq += 1
			else:
				currSeq = 1
			maxSeq = max(currSeq, maxSeq)
		return maxSeq


class Solution:

	def findLongestConseqSubseq(self, arr, N):
		arr.sort()
		ans = 1
		max_ans = 1
		for i in range(N - 1):
			if arr[i] == arr[i + 1] - 1:
				ans += 1
				max_ans = max(ans, max_ans)
			elif arr[i] == arr[i + 1]:
				continue
			else:
				ans = 1
		return max_ans


class Solution:

	def findLongestConseqSubseq(self, arr, N):
		seen = set(arr)
		mx = -float('inf')
		for i in range(len(arr)):
			num = arr[i]
			count = 1
			while num - 1 in seen:
				count += 1
				num -= 1
			mx = max(mx, count)
		return mx


class Solution:

	def findLongestConseqSubseq(self, arr, N):
		maxi = 0
		count = 0
		arr.sort()
		nums = []
		nums.append(arr[0])
		for i in range(1, N):
			if arr[i] != arr[i - 1]:
				nums.append(arr[i])
		for i in range(len(nums)):
			if i > 0 and nums[i] == nums[i - 1] + 1:
				count += 1
			else:
				count = 1
			maxi = max(maxi, count)
		return maxi


class Solution:

	def findLongestConseqSubseq(self, arr, N):
		s = set(arr)
		count = 0
		for i in s:
			if i - 1 not in s:
				val = i
				while val in s:
					val += 1
				count = max(count, val - i)
		return count


class Solution:

	def findLongestConseqSubseq(self, arr, N):
		s = set(arr)
		max = 1
		c = 1
		for i in s:
			while i + 1 in s:
				c = c + 1
				i = i + 1
				if c > max:
					max = c
			c = 1
		return max


class Solution:

	def findLongestConseqSubseq(self, arr, N):
		s = set(arr)
		curr = 1
		res = 1
		for i in s:
			if i - 1 not in s:
				x = i + 1
				curr = 1
				while x in s:
					curr += 1
					x += 1
			res = max(curr, res)
		return res


from sortedcontainers import SortedList, SortedSet

class Solution:

	def findLongestConseqSubseq(self, arr, n):
		s = SortedSet(arr)
		c = 0
		m = 0
		for si in s:
			if si - 1 in s:
				c += 1
			else:
				m = max(m, c)
				c = 1
		m = max(m, c)
		return m


class Solution:

	def findLongestConseqSubseq(self, arr, N):
		count = 1
		maxLength = 1
		arr.sort()
		unique = [arr[0]]
		for i in range(1, len(arr)):
			if arr[i] != arr[i - 1]:
				unique.append(arr[i])
		for i in range(len(unique)):
			if i > 0 and unique[i - 1] + 1 == unique[i]:
				count += 1
			else:
				count = 1
			maxLength = max(count, maxLength)
		return maxLength


from collections import Counter

class Solution:

	def findLongestConseqSubseq(self, arr, N):
		d = Counter(arr)
		ans = 1
		for i in arr:
			if i - 1 in d:
				cnt = 0
				j = i
				while j in d:
					cnt += 1
					j -= 1
				ans = max(ans, cnt)
		return ans


class Solution:

	def findLongestConseqSubseq(self, arr, N):
		d = set(arr)
		counter = 1
		max_value = 1
		for x in d:
			while x + 1 in d:
				x += 1
				counter += 1
				if counter > max_value:
					max_value = counter
			counter = 1
		return max_value


class Solution:

	def findLongestConseqSubseq(self, arr, N):
		s = {}
		for i in arr:
			s[i] = 1
		ans = 0
		for i in range(n):
			if arr[i] - 1 not in s:
				j = arr[i]
				while j in s:
					j += 1
				ans = max(ans, j - arr[i])
		return ans


class Solution:

	def findLongestConseqSubseq(self, arr, N):
		d = {}
		c = 0
		cc = 1
		l = []
		arr = sorted(arr)
		for i in arr:
			l.append(i)
			if i not in d:
				d[i] = 1
			else:
				d[i] += 1
		for i in range(len(l)):
			c = c + d[l[i]]
			if i + 1 < len(l) and l[i] + 1 == l[i + 1]:
				pass
			else:
				cc = max(cc, c)
				c = 0
		return cc


class Solution:

	def findLongestConseqSubseq(self, arr, N):
		s = set(arr)
		maxn = 0
		for i in range(n):
			if arr[i] - 1 not in s:
				ml = 0
				while arr[i] + ml in s:
					ml += 1
				maxn = max(maxn, ml)
		return maxn


class Solution:

	def findLongestConseqSubseq(self, arr, N):
		s = set(arr)
		mcount = 0
		for i in range(0, len(arr)):
			if arr[i] in s:
				if arr[i] - 1 in s:
					pass
				else:
					count = 1
					a = True
					j = 1
					while a == True:
						if arr[i] + j in s:
							count += 1
							j += 1
						else:
							a = False
					if mcount < count:
						mcount = count
		return mcount


class Solution:

	def findLongestConseqSubseq(self, arr, N):
		c = 0
		k = 0
		maxi = [1 for i in arr]
		arr.sort()
		for i in range(0, n - 1):
			if arr[i + 1] == arr[i] + 1:
				maxi[k] += 1
			else:
				k = k + 1
		return max(maxi)


class Solution:

	def findLongestConseqSubseq(self, arr, N):
		arr.sort()
		l = []
		for i in range(len(arr)):
			k = [arr[i]]
			for j in range(i + 1, len(arr)):
				if arr[j] == k[-1] + 1:
					k.append(arr[j])
				else:
					break
			l.append(k)
		l.sort(key=len)
		return len(l[-1])


class Solution:

	def findLongestConseqSubseq(self, arr, N):
		collection = set()
		for i in arr:
			collection.add(i)
		visited = set()
		max_result = 0
		count = 0
		for nums in arr:
			if nums in visited:
				continue
			while nums in collection:
				visited.add(nums)
				nums += 1
				count += 1
			max_result = max(max_result, count)
			count = 0
		return max_result


class Solution:

	def findLongestConseqSubseq(self, arr, N):
		arr = set(arr)
		c = 1
		res = 1
		for i in arr:
			if i - 1 not in arr:
				mini = i
				c = 1
				while mini + 1 in arr:
					c += 1
					mini += 1
				res = max(res, c)
		return res


class Solution:

	def findLongestConseqSubseq(self, arr, N):
		hashset = set(arr)
		longest = 1
		cnt = 1
		for i in hashset:
			cnt = 1
			if i - 1 in hashset:
				cnt = 1
			else:
				while i + 1 in hashset:
					cnt += 1
					i += 1
			longest = max(longest, cnt)
		return longest


class Solution:

	def findLongestConseqSubseq(self, arr, N):
		arr.sort()
		count = 1
		max_ = 1
		for i in range(len(arr) - 1):
			if arr[i] == arr[i + 1] - 1:
				count += 1
			if arr[i] == arr[i + 1]:
				continue
			if arr[i] != arr[i + 1] - 1:
				count = 1
			if count > max_:
				max_ = count
		return max_


class Solution(object):

	def findLongestConseqSubseq(self, nums, N):
		if N == 0:
			return 0
		(maxLen, lookup) = (1, set())
		for num in nums:
			lookup.add(num)
		for num in nums:
			if num - 1 not in lookup:
				currLen = 1
				while num + 1 in lookup:
					num += 1
					currLen += 1
					maxLen = max(maxLen, currLen)
		return maxLen


class Solution:

	def findLongestConseqSubseq(self, arr, N):
		nums = arr
		hashSet = set()
		for num in nums:
			hashSet.add(num)
		longestStreak = 0
		for num in nums:
			if num - 1 not in hashSet:
				currentNum = num
				currentStreak = 1
				while currentNum + 1 in hashSet:
					currentNum += 1
					currentStreak += 1
				longestStreak = max(longestStreak, currentStreak)
		return longestStreak


class Solution:

	def findLongestConseqSubseq(self, arr, N):
		dict1 = {}
		lst = []
		arr = sorted(arr)
		longest = 1
		count = 1
		for i in range(N - 1):
			if abs(arr[i] - arr[i + 1]) == 1:
				count = count + 1
			elif abs(arr[i] - arr[i + 1]) > 1:
				count = 1
			longest = max(longest, count)
		return longest


class Solution:

	def findLongestConseqSubseq(self, arr, N):
		a = arr
		n = N
		a = sorted(a)
		lastsmaller = float('-inf')
		cntcurr = 1
		longest = 1
		for i in range(n):
			if a[i] - lastsmaller == 1:
				cntcurr += 1
			elif a[i] - lastsmaller == 0:
				cntcurr = cntcurr
			else:
				cntcurr = 1
			lastsmaller = a[i]
			longest = max(cntcurr, longest)
		return longest


class Solution:

	def findLongestConseqSubseq(self, arr, N):
		arr = set(arr)
		arr = list(arr)
		arr.sort()
		if len(arr) == 1:
			ans = 1
		else:
			ans = 0
		count = 1
		for i in range(1, len(arr)):
			if i > 0 and arr[i - 1] + 1 == arr[i]:
				count += 1
			else:
				count = 1
			ans = max(ans, count)
		return ans


class Solution:

	def findLongestConseqSubseq(self, arr, N):
		st = set(arr)
		ans = 1
		for y in arr:
			x = y
			if x - 1 not in st:
				c = 1
				while x + 1 in st:
					x += 1
					c += 1
				ans = max(ans, c)
		return ans


class Solution:

	def findLongestConseqSubseq(self, arr, N):
		max_length = 0
		num_set = set(arr)
		for num in num_set:
			if num - 1 not in num_set:
				current_length = 1
				while num + 1 in num_set:
					current_length += 1
					num += 1
				max_length = max(max_length, current_length)
		return max_length


class Solution:

	def findLongestConseqSubseq(self, arr, N):
		arr.sort()
		longest = 1
		cnt = 0
		lastSmaller = -sys.maxsize - 1
		for i in range(N):
			if arr[i] - 1 == lastSmaller:
				cnt += 1
				lastSmaller = arr[i]
			elif arr[i] != lastSmaller:
				cnt = 1
				lastSmaller = arr[i]
			longest = max(longest, cnt)
		return longest


class Solution:

	def findLongestConseqSubseq(self, arr, N):
		sai = set()
		for i in range(N):
			sai.add(arr[i])
		res = 1
		for i in arr:
			if i - 1 not in sai:
				curr = 1
				while curr + i in sai:
					curr += 1
				res = max(res, curr)
		return res


import sys

class Solution:

	def findLongestConseqSubseq(self, arr, N):
		n = len(arr)
		s = set(arr)
		maxCount = 0
		for num in arr:
			if num - 1 not in s:
				count = 1
				while num + 1 in s:
					count += 1
					num += 1
				maxCount = max(maxCount, count)
		return maxCount


class Solution:

	def findLongestConseqSubseq(self, arr, N):
		s = set(arr)
		longest = 0
		for i in range(N):
			if arr[i] - 1 not in s:
				l = 0
				while arr[i] + l in s:
					l += 1
				longest = max(longest, l)
		return longest


class Solution:

	def findLongestConseqSubseq(self, arr, N):
		d = {}
		for i in range(N):
			d[arr[i]] = i
		ans = 0
		for i in range(N):
			if arr[i] > 0:
				count = 0
				t = arr[i]
				arr[i] *= -1
				c = 1
				x = t
				while x - 1 in d:
					arr[d[x - 1]] *= -1
					x -= 1
					c += 1
				x = t
				while x + 1 in d:
					arr[d[x + 1]] *= -1
					x += 1
					c += 1
				ans = max(ans, c)
		return ans


class Solution:

	def findLongestConseqSubseq(self, nums, N):
		ans = 0
		hashset = set()
		for i in nums:
			hashset.add(i)
		for i in nums:
			if i - 1 not in hashset:
				num = i
				cur = 1
				while num + 1 in hashset:
					cur = cur + 1
					num = num + 1
				ans = max(cur, ans)
		return ans


class Solution:

	def findLongestConseqSubseq(self, nums, N):
		nums.sort()
		ans = 0
		cur = 1
		i = 1
		while i < N:
			if nums[i] == nums[i - 1] + 1:
				cur += 1
			elif nums[i] - nums[i - 1] > 1:
				ans = max(ans, cur)
				cur = 1
			i += 1
		ans = max(ans, cur)
		return ans


class Solution:

	def findLongestConseqSubseq(self, arr, N):
		result = 1
		count = 1
		arr = sorted(arr)
		for i in range(N - 1):
			if arr[i] + 1 == arr[i + 1]:
				count += 1
			elif arr[i] == arr[i + 1]:
				continue
			else:
				count = 1
			result = max(result, count)
		return result


class Solution:

	def findLongestConseqSubseq(self, arr, N):
		numSet = set(arr)
		longest = 0
		for num in arr:
			if num - 1 not in numSet:
				length = 0
				while num + length in numSet:
					length += 1
				longest = max(length, longest)
		return longest


class Solution:

	def findLongestConseqSubseq(self, arr, N):
		arrset = set(arr)
		i = 0
		res = 0
		for i in arr:
			if i - 1 not in arrset:
				length = 1
				while i + length in arrset:
					length += 1
				res = max(res, length)
		return res


class Solution:

	def findLongestConseqSubseq(self, arr, N):
		arr = sorted(arr)
		maxc = 1
		curr = 0
		least = -1
		for i in range(N):
			if arr[i] - 1 == least:
				curr += 1
				least = arr[i]
			elif arr[i] != least:
				least = arr[i]
				curr = 1
			maxc = max(maxc, curr)
		return maxc


class Solution:

	def findLongestConseqSubseq(self, arr, N):
		from collections import Counter
		dic = dict(Counter(arr))
		longseq = 0
		for i in arr:
			curseq = 0
			if i - 1 not in dic:
				curnum = i
				curseq = 1
				while curnum + 1 in dic:
					curnum += 1
					curseq += 1
			longseq = max(longseq, curseq)
		return longseq


class Solution:

	def findLongestConseqSubseq(self, arr, N):
		num_set = set(arr)
		ma = 0
		for e in num_set:
			if e - 1 not in num_set:
				k = e
				c = 0
				while k in num_set:
					k += 1
					c += 1
				ma = max(c, ma)
		return ma


class Solution:

	def findLongestConseqSubseq(self, arr, N):
		num_set = set(arr)
		longest_seq = 0
		for num in num_set:
			if num - 1 not in num_set:
				current_num = num
				current_seq = 1
				while current_num + 1 in num_set:
					current_num += 1
					current_seq += 1
				longest_seq = max(longest_seq, current_seq)
		return longest_seq