Given an integer array arr and an integer difference, return the length of the longest subsequence in arr which is an arithmetic sequence such that the difference between adjacent elements in the subsequence equals difference.
 
Example 1:
Input: arr = [1,2,3,4], difference = 1
Output: 4
Explanation: The longest arithmetic subsequence is [1,2,3,4].
Example 2:
Input: arr = [1,3,5,7], difference = 1
Output: 1
Explanation: The longest arithmetic subsequence is any single element.

Example 3:
Input: arr = [1,5,7,8,5,3,4,2,1], difference = -2
Output: 4
Explanation: The longest arithmetic subsequence is [7,5,3,1].

 
Constraints:

1 <= arr.length <= 10^5
-10^4 <= arr[i], difference <= 10^4

Difficulty: MEDIUM
Tags: Dynamic programming

Data structures
Skill types: Dynamic programming

Data structures

Starter code:
class Solution:
    def longestSubsequence(self, arr: List[int], difference: int) -> int:
        

Solutions:
from collections import defaultdict

class Solution:

	def longestSubsequence(self, arr: List[int], difference: int) -> int:
		count_dict = defaultdict(int)
		for num in arr:
			count_dict[num] = count_dict[num - difference] + 1
		return max(count_dict.values())


class Solution:

	def longestSubsequence(self, arr: List[int], difference: int) -> int:
		hs = dict()
		for num in arr:
			if num - difference in hs:
				hs[num] = hs[num - difference] + 1
			if num not in hs and num - difference not in hs:
				hs[num] = 1
		return max((item for item in hs.values()))


from collections import defaultdict

class Solution:

	def longestSubsequence(self, arr: List[int], difference: int) -> int:
		if not arr:
			return 0
		dp = [1 for _ in range(len(arr))]
		seen = defaultdict(list)
		for (i, num) in enumerate(arr):
			prev = num - difference
			choices = seen[prev]
			for j in choices:
				dp[i] = max(dp[j] + 1, dp[i])
			seen[num].append(i)
		return max(dp)


class Solution:

	def longestSubsequence(self, arr: List[int], difference: int) -> int:
		dp = [1 for a in arr]
		ele = collections.defaultdict(list)
		for (i, x) in enumerate(arr):
			ele[x].append(i)
		for (i, a) in enumerate(arr):
			if a - difference in ele:
				for j in ele[a - difference]:
					if j < i:
						dp[i] = max(dp[j] + 1, dp[i])
		return max(dp)


class Solution:

	def longestSubsequence(self, arr: List[int], difference: int) -> int:
		seen = Counter()
		for v in arr:
			seen[v] = seen[v - difference] + 1
		return max(seen.values())


class Solution:

	def longestSubsequence(self, arr: List[int], diff: int) -> int:
		mx = max(arr)
		mn = min(arr)
		d = dict()
		for i in range(-10 ** 4, 10 ** 4 + 1):
			d[i] = 0
		n = len(arr)
		if diff > 0:
			d[arr[0]] = 1
			for i in range(1, n):
				if arr[i] - diff >= mn:
					d[arr[i]] = max(d[arr[i]], d[arr[i] - diff] + 1)
				else:
					d[arr[i]] = 1
		else:
			arr = arr[::-1]
			d[arr[0]] = 1
			for i in range(1, n):
				if arr[i] + diff >= mn:
					d[arr[i]] = max(d[arr[i]], d[arr[i] + diff] + 1)
				else:
					d[arr[i]] = 1
		return max(list(d.values()))


class Solution:

	def longestSubsequence(self, arr: List[int], difference: int) -> int:
		d = dict()
		ret = 0
		for (i, n) in enumerate(arr):
			if n - difference not in d:
				d[n] = 1
			else:
				d[n] = d[n - difference] + 1
			ret = max(ret, d[n])
		return ret


class Solution:

	def longestSubsequence(self, arr: List[int], difference: int) -> int:
		current = {}
		for x in arr:
			old = x - difference
			if old in current:
				count = current[old]
				del current[old]
				current[x] = count + 1
			elif x not in current:
				current[x] = 1
		return max(current.values())


class Solution:

	def longestSubsequence(self, arr: List[int], difference: int) -> int:
		sub_dict = {}
		n = len(arr)
		if n == 0:
			return 0
		if n == 1:
			return 1
		max_len = 1
		for i in range(n - 1, -1, -1):
			value = arr[i]
			new_k_v = []
			dd = value + difference
			if dd in sub_dict:
				sub_dict[value] = max(sub_dict.get(value, 0), sub_dict[dd] + 1)
				max_len = max(sub_dict[value], max_len)
			if value not in sub_dict:
				sub_dict[value] = 1
		return max_len


class Solution:

	def longestSubsequence(self, arr: List[int], difference: int) -> int:
		res = {}
		for num in arr:
			if num - difference in res:
				res[num] = res[num - difference] + 1
			else:
				res[num] = 1
		return max(res.values())


class Solution:

	def longestSubsequence(self, arr: List[int], difference: int) -> int:
		res = dict()
		max_seq = 0
		for a in arr:
			res[a] = res.get(a - difference, 0) + 1
		return max(res.values())


class Solution:

	def longestSubsequence(self, arr: List[int], difference: int) -> int:
		dp = [0] * 40001
		d = 20000
		opt = 0
		for e in arr:
			dp[e + d] = dp[e - difference + d] + 1
			opt = max(opt, dp[e + d])
		return opt


class Solution:

	def longestSubsequence(self, arr: List[int], difference: int) -> int:
		dp = [0 for _ in range(len(arr))]
		lookup = {}
		for i in range(len(arr)):
			if arr[i] not in lookup:
				lookup[arr[i]] = [i]
			else:
				lookup[arr[i]].append(i)
		for i in range(len(arr) - 1, 0, -1):
			if arr[i] - difference in lookup:
				dp[i] = max(1, dp[i])
				for index in lookup[arr[i] - difference]:
					if index < i:
						dp[index] = dp[i] + 1
		return max(dp) if max(dp) > 0 else 1


class Solution:

	def longestSubsequence(self, arr: List[int], d: int) -> int:
		if not arr:
			return 0
		cache = {}
		maxc = 0
		for i in arr:
			if i - d in cache:
				cache[i] = cache[i - d] + 1
			else:
				cache[i] = 1
			maxc = max(maxc, cache[i])
		return maxc


class Solution:

	def longestSubsequence(self, arr: List[int], difference: int) -> int:
		n = len(arr)
		dp = {}
		for i in range(n):
			if arr[i] - difference in dp:
				dp[arr[i]] = dp[arr[i] - difference] + 1
			else:
				dp[arr[i]] = 1
		return max(dp.values())


class Solution:

	def longestSubsequence(self, arr: List[int], difference: int) -> int:
		m = dict()
		for (ind, num) in enumerate(arr):
			if num in m:
				m[num].append(ind)
			else:
				m[num] = [ind]
		dp = []
		longest = 1
		for (ind, num) in enumerate(arr):
			if num - difference in m:
				possible_sol = []
				for diff_ind in m[num - difference]:
					if diff_ind < len(dp):
						possible_sol.append(dp[diff_ind] + 1)
				if possible_sol == []:
					dp.append(1)
				else:
					curr_max = max(possible_sol)
					dp.append(curr_max)
					if curr_max > longest:
						longest = curr_max
			else:
				dp.append(1)
		return longest


class Solution:

	def longestSubsequence(self, arr: List[int], difference: int) -> int:
		dic = {}
		for i in range(len(arr)):
			temp = False
			if arr[i] - difference in list(dic.keys()):
				dic[arr[i]] = dic[arr[i] - difference] + [arr[i]]
				if arr[i] != arr[i] - difference:
					dic.pop(arr[i] - difference)
				temp = True
			elif arr[i] in list(dic.keys()):
				temp = True
			if not temp:
				dic[arr[i]] = [arr[i]]
		return max(list([len(x) for x in list(dic.values())]))


class Solution:

	def longestSubsequence(self, arr: List[int], difference: int) -> int:
		dp = defaultdict(int)
		for (i, elem) in enumerate(arr):
			dp[elem] = 1 + dp[elem - difference]
		maxElem = 0
		for key in dp:
			maxElem = max(maxElem, dp[key])
		return maxElem


from collections import defaultdict

class Solution:

	def longestSubsequence(self, arr: List[int], difference: int) -> int:
		n = len(arr)
		ret = 0
		mappings = defaultdict(list)
		for (i, v) in enumerate(arr):
			mappings[v].append(i)
		M = [-1 for i in range(n)]

		def dp(i):
			if i == n - 1:
				return 1
			if M[i] != -1:
				return M[i]
			M[i] = 1
			for j in mappings[arr[i] + difference]:
				if j > i:
					M[i] += dp(j)
					break
			return M[i]
		for i in range(n):
			ret = max(ret, dp(i))
		return ret


class Solution:

	def longestSubsequence(self, arr: List[int], diff: int) -> int:
		mx = -float('inf')
		mn = float('inf')
		n = 0
		for i in arr:
			mx = max(mx, i)
			mn = min(mn, i)
			n += 1
		d = dict()
		for i in range(mn, mx + 1):
			d[i] = 0
		if diff > 0:
			d[arr[0]] = 1
			for i in range(1, n):
				if arr[i] - diff >= mn:
					d[arr[i]] = max(d[arr[i]], d[arr[i] - diff] + 1)
				else:
					d[arr[i]] = 1
		else:
			arr = arr[::-1]
			d[arr[0]] = 1
			for i in range(1, n):
				if arr[i] + diff >= mn:
					d[arr[i]] = max(d[arr[i]], d[arr[i] + diff] + 1)
				else:
					d[arr[i]] = 1
		return max(list(d.values()))


class Solution:

	def longestSubsequence(self, arr: List[int], difference: int) -> int:
		mp = {}
		res = 0
		for num in arr:
			currlen = 1
			if num - difference in mp:
				currlen = mp[num - difference] + 1
			mp[num] = max(mp.get(num, 1), currlen)
			res = max(res, currlen)
		return res


class Solution:

	def longestSubsequence(self, arr: List[int], difference: int) -> int:
		if len(arr) == 1:
			return 1
		memo = {}
		res = 0
		for i in range(len(arr) - 1, -1, -1):
			if arr[i] + difference not in memo:
				memo[arr[i]] = 1
			else:
				memo[arr[i]] = memo[arr[i] + difference] + 1
			res = max(res, memo[arr[i]])
		return res


from collections import defaultdict

def lis(a, diff):
	lis = {}
	for i in range(len(a)):
		lis[a[i]] = lis.get(a[i] - diff, 0) + 1
	return max(lis.values())

class Solution:

	def longestSubsequence(self, arr: List[int], difference: int) -> int:
		return lis(arr, difference)


class Solution:

	def longestSubsequence(self, arr: List[int], diff: int) -> int:
		indexMap = defaultdict(list)
		dp = [0] * len(arr)
		maxSeq = 0
		for (i, num) in enumerate(arr):
			if num - diff in indexMap:
				for newIndex in indexMap[num - diff]:
					dp[i] = max(dp[i], dp[newIndex])
			dp[i] += 1
			maxSeq = max(maxSeq, dp[i])
			indexMap[num].append(i)
		return maxSeq


class Solution:

	def longestSubsequence(self, arr: List[int], difference: int) -> int:
		max_val = 10000
		min_val = -10000
		diff = [0 for i in range(max_val - min_val + 1)]
		res = 1
		for x in arr:
			if x - difference >= min_val and x - difference <= max_val and (diff[x - difference + max_val] >= diff[x + max_val]):
				diff[x + max_val] = diff[x - difference + max_val] + 1
			else:
				diff[x + max_val] = max(1, diff[x + max_val])
			res = max(res, diff[x + max_val])
		return res


class Solution:

	def longestSubsequence(self, arr: List[int], difference: int) -> int:
		dp = {}
		maxs = 1
		for num in arr:
			dp[num] = dp.get(num - difference, 0) + 1
			if dp[num] > maxs:
				maxs = dp[num]
		return maxs


class Solution:

	def longestSubsequence(self, arr: List[int], difference: int) -> int:
		memo = Counter()
		for a in arr:
			memo[a] = memo[a - difference] + 1
		return max(memo.values())


class Solution:

	def longestSubsequence(self, arr: List[int], difference: int) -> int:
		ans = 1
		table = {}
		for a in arr:
			prev = a - difference
			if prev in table:
				table[a] = table[prev] + 1
			else:
				table[a] = 1
			ans = max(ans, table[a])
		return ans


class Solution:

	def longestSubsequence(self, arr: List[int], difference: int) -> int:
		if not arr:
			return 0
		dp = dict()
		for num in arr:
			prev = num - difference
			if prev in dp:
				dp[num] = 1 + dp.get(prev, 0)
			else:
				dp[num] = 1
		return max(dp.values())


class Solution:

	def longestSubsequence(self, arr: List[int], difference: int) -> int:
		dp = [1] * len(arr)
		ans = 1
		seen = {}
		for i in range(len(arr)):
			if arr[i] - difference in seen:
				dp[i] = 1 + dp[seen[arr[i] - difference]]
			seen[arr[i]] = i
		return max(dp)


class Solution:

	def longestSubsequence(self, arr: List[int], difference: int) -> int:
		mp = collections.defaultdict(int)
		ans = 0
		for a in arr:
			mp[a] = 1 + mp[a - difference]
			ans = max(ans, mp[a])
		return ans


class Solution:

	def longestSubsequence(self, arr: List[int], difference: int) -> int:
		n = len(arr)
		dp = defaultdict(int)
		for i in arr:
			dp[i] = max(dp[i], dp[i - difference] + 1)
		return max(dp.values())


class Solution:

	def longestSubsequence(self, arr: List[int], d: int) -> int:
		cnt = defaultdict(int)
		for i in arr:
			cnt[i] = cnt[i - d] + 1
		return max(cnt.values())


class Solution:

	def longestSubsequence(self, arr: List[int], difference: int) -> int:
		(dp, res) = ({}, 0)
		for i in arr:
			dp[i] = dp.get(i - difference, 0) + 1
			res = max(res, dp[i])
		return res


class Solution:

	def longestSubsequence(self, arr: List[int], difference: int) -> int:
		if len(arr) == 1:
			return 1
		dp = [1] * len(arr)
		dic = {arr[0]: 0}
		for i in range(1, len(dp)):
			dic[arr[i]] = i
			if arr[i] - difference in dic:
				dp[i] = max(dp[i], dp[dic[arr[i] - difference]] + 1)
		return max(dp)


class Solution:

	def longestSubsequence(self, arr: List[int], d: int) -> int:
		memo = dict()
		for a in arr:
			if a - d in list(memo.keys()):
				memo[a] = memo[a - d] + 1
			else:
				memo[a] = 1
		return max(list(memo.values()))


class Solution:

	def longestSubsequence(self, arr: List[int], difference: int) -> int:
		dp = {}
		l = len(arr)
		index_map = {}
		for i in range(l):
			if arr[i] - difference in index_map:
				j = index_map[arr[i] - difference]
				dp[i] = dp.get(j, 1) + 1
			index_map[arr[i]] = i
		return max(dp.values()) if dp else 1


from collections import defaultdict

class Solution:

	def longestSubsequence(self, arr: List[int], difference: int) -> int:
		elemToLen = defaultdict(int)
		best = 0
		for x in arr:
			elemToLen[x] = max(elemToLen[x], elemToLen[x - difference] + 1)
			best = max(best, elemToLen[x])
		return best


class Solution:

	def longestSubsequence(self, arr: List[int], difference: int) -> int:
		dp = {}
		l = len(arr)
		index_map = {}
		res = 1
		for i in range(l):
			if arr[i] - difference in index_map:
				j = index_map[arr[i] - difference]
				dp[i] = dp.get(j, 1) + 1
				if dp[i] > res:
					res = dp[i]
			index_map[arr[i]] = i
		return res


class Solution:

	def longestSubsequence(self, arr: List[int], difference: int) -> int:
		if not arr:
			return 0
		max_len = 0
		dp = [0] * len(arr)
		prev_max_len = {}
		for (i, num) in enumerate(arr):
			if (key := (arr[i] - difference)) in prev_max_len:
				dp[i] = prev_max_len[key] + 1
			else:
				dp[i] = 1
			prev_max_len[arr[i]] = dp[i]
			max_len = max(max_len, dp[i])
		return max_len


class Solution:

	def longestSubsequence(self, arr: List[int], difference: int) -> int:
		mem = collections.defaultdict(int)
		res = 0
		for n in arr:
			if mem[n - difference] + 1 > mem[n]:
				mem[n] = mem[n - difference] + 1
			res = max(res, mem[n])
		return res


class Solution:

	def longestSubsequence(self, arr: List[int], diff: int) -> int:
		res = {}
		for num in arr:
			res[num] = res.get(num - diff, 0) + 1
		return max(res.values())


class Solution:

	def longestSubsequence(self, arr: List[int], difference: int) -> int:
		cnt = collections.Counter()
		ans = 0
		for num in arr:
			cnt[num] = cnt[num - difference] + 1
			ans = max(ans, cnt[num])
		return ans


class Solution:
	import collections

	def longestSubsequence(self, arr: List[int], difference: int) -> int:
		dp = {}
		max_len = 0
		for i in arr:
			dp[i] = dp.get(i - difference, 0) + 1
			max_len = max(max_len, dp[i])
		return max_len


import collections

class Solution:

	def longestSubsequence(self, arr: List[int], difference: int) -> int:
		prev_seq = collections.defaultdict(int)
		max_seq = 1
		for x in reversed(arr):
			target = x + difference
			x_seq = prev_seq[target] + 1
			max_seq = max(max_seq, x_seq)
			prev_seq[x] = max(prev_seq[x], x_seq)
		return max_seq


class Solution:

	def longestSubsequence(self, arr: List[int], difference: int) -> int:
		tail = collections.Counter()
		maxi = 1
		for n in arr:
			if n - difference in tail:
				maxi = max(maxi, tail[n - difference] + 1)
				tail[n] = tail[n - difference] + 1
			else:
				tail[n] = 1
		return maxi


class Solution:

	def longestSubsequence(self, arr: List[int], difference: int) -> int:
		count = Counter(arr)
		if difference == 0:
			return max(count.values())
		n = len(arr)
		dd = dict()
		ans = 1
		for (i, n) in enumerate(arr):
			if n - difference in dd:
				dd[n] = 1 + dd[n - difference]
			else:
				dd[n] = 1
			ans = max(ans, dd[n])
		return ans


from collections import defaultdict

class Solution:

	def longestSubsequence(self, arr: List[int], difference: int) -> int:
		prev_elem_dict = defaultdict(int)
		result = 0
		for num in arr:
			prev_elem_dict[num] = max(prev_elem_dict[num], prev_elem_dict[num - difference] + 1)
			result = max(result, prev_elem_dict[num])
		return result


class Solution:

	def longestSubsequence(self, arr: List[int], difference: int) -> int:
		a = len(arr)
		dp = {}
		ans = 0
		for value in arr:
			targetValue = value - difference
			if targetValue in dp:
				dp[value] = 1 + dp[targetValue]
			else:
				dp[value] = 1
			ans = max(ans, dp[value])
		return ans


class Solution:

	def longestSubsequence(self, arr: List[int], difference: int) -> int:
		num2len = dict()
		res = 0
		for i in range(len(arr)):
			if arr[i] - difference in num2len:
				num2len[arr[i]] = num2len[arr[i] - difference] + 1
			else:
				num2len[arr[i]] = 1
			res = max(res, num2len[arr[i]])
		return res


class Solution:

	def longestSubsequence(self, arr: List[int], diff: int) -> int:
		n = len(arr)
		ans = 1
		hmap = {arr[0]: 1}
		for i in range(1, n):
			hmap[arr[i]] = 1
			if arr[i] - diff in hmap:
				hmap[arr[i]] = max(hmap[arr[i]], hmap[arr[i] - diff] + 1)
			ans = max(ans, hmap[arr[i]])
		return ans


import bisect

class Solution:

	def longestSubsequence(self, arr, diff):
		dp = {}
		ans = 0
		for i in arr:
			if i - diff in dp:
				dp[i] = dp[i - diff] + 1
			else:
				dp[i] = 1
			ans = max(ans, dp[i])
		return ans


class Solution:

	def longestSubsequence(self, arr: List[int], diff: int) -> int:
		n = len(arr)
		dp = dict()
		for i in range(n):
			if arr[i] - diff in dp:
				if arr[i] in dp:
					dp[arr[i]] = max(dp[arr[i]], dp[arr[i] - diff] + 1)
				else:
					dp[arr[i]] = dp[arr[i] - diff] + 1
			elif arr[i] in dp:
				dp[arr[i]] = max(dp[arr[i]], 1)
			else:
				dp[arr[i]] = 1
		return max(dp.values())


class Solution:

	def longestSubsequence(self, arr: List[int], difference: int) -> int:
		(d, ans) = (defaultdict(int), 0)
		for i in arr:
			d[i] = d[i - difference] + 1
			ans = max(ans, d[i])
		return ans


class Solution:

	def longestSubsequence(self, arr: List[int], diff: int) -> int:
		(dp, ans) = (dict(), 0)
		for i in arr:
			dp[i] = dp.get(i - diff, 0) + 1
			ans = max(ans, dp[i])
		return ans


class Solution:

	def longestSubsequence(self, arr: List[int], difference: int) -> int:
		d = {}
		mx = 1
		for (i, e) in enumerate(arr):
			k = e + -difference
			if k in d:
				d[e] = d[k] + 1
				mx = max(mx, d[e])
			if e not in d:
				d[e] = 1
		return mx


class Solution:

	def longestSubsequence(self, arr: List[int], difference: int) -> int:
		d = {}
		res = 0
		for i in arr:
			if i - difference in d:
				d[i] = 1 + d.pop(i - difference)
			elif i not in d:
				d[i] = 1
			res = max(res, d[i])
		return res


class Solution:

	def longestSubsequence(self, arr: List[int], difference: int) -> int:
		dp = {}
		for a in arr:
			dp[a] = dp.get(a - difference, 0) + 1
		return max(dp.values())


class Solution:

	def longestSubsequence(self, arr: List[int], difference: int) -> int:
		dp = collections.defaultdict(int)
		ans = 0
		for element in arr:
			dp[element] = dp[element - difference] + 1
			ans = max(dp[element], ans)
		return ans


class Solution:

	def longestSubsequence(self, arr: List[int], d: int) -> int:
		if not arr:
			return 0
		maxlen = 1
		helper = {}
		for (i, x) in enumerate(arr):
			if x - d in helper:
				helper[x] = helper[x - d] + 1
			else:
				helper[x] = 1
			maxlen = max(maxlen, helper[x])
		return maxlen


class Solution:

	def longestSubsequence(self, arr: List[int], difference: int) -> int:
		(dp, res) = (collections.defaultdict(int), 0)
		for x in arr:
			dp[x] = max(1, dp[x])
			res = max(res, dp[x])
			dp[x + difference] = max(dp[x + difference], dp[x] + 1)
		return res


class Solution:

	def longestSubsequence(self, arr: List[int], difference: int) -> int:
		states = collections.defaultdict(int)
		for a in arr:
			states[a] = states[a - difference] + 1
		return max(states.values())


class Solution:

	def longestSubsequence(self, arr: List[int], difference: int) -> int:
		dp = {}
		res = 1
		for i in arr:
			comp = i - difference
			if comp in dp:
				dp[i] = dp[comp] + 1
				res = max(res, dp[i])
			else:
				dp[i] = 1
		return res


from collections import defaultdict

class Solution:

	def longestSubsequence(self, arr: List[int], difference: int) -> int:
		currentMax = 0
		dictionary = defaultdict(int)
		for i in range(len(arr)):
			dictionary[arr[i]] = dictionary[arr[i] - difference] + 1
		for e in dictionary:
			currentMax = max(dictionary[e], currentMax)
		return currentMax


class Solution:

	def longestSubsequence(self, arr: List[int], difference: int) -> int:
		if difference < 0:
			return self.longestSubsequence(arr[::-1], -difference)
		minim = 0
		for i in range(0, len(arr)):
			minim = min(arr[i], minim)
		maxim = arr[0]
		for i in range(0, len(arr)):
			arr[i] = arr[i] - minim
			maxim = max(maxim, arr[i])
		indices = [-1] * (maxim + difference + 1)
		dp = [0] * len(arr)
		i = len(arr) - 1
		while i >= 0:
			if indices[arr[i] + difference] != -1:
				dp[i] = 1 + dp[indices[arr[i] + difference]]
			else:
				dp[i] = 1
			indices[arr[i]] = i
			i = i - 1
		ans = -1
		for i in range(0, len(dp)):
			ans = max(ans, dp[i])
		return ans


class Solution:

	def longestSubsequence(self, arr: List[int], difference: int) -> int:
		if len(arr) == 1:
			return 1
		(res, length) = (1, len(arr))
		dp = {}
		dp[arr[-1]] = 1
		flag = 1
		for i in range(length - 2, -1, -1):
			if arr[i] not in dp:
				dp[arr[i]] = 1
				flag = 0
			if arr[i] + difference in dp:
				if difference == 0 and flag == 0:
					flag = 1
					continue
				dp[arr[i]] = max(dp[arr[i]], dp[arr[i] + difference] + 1)
			res = max(res, dp[arr[i]])
		return res


class Solution:

	def longestSubsequence(self, arr: List[int], difference: int) -> int:
		subseqs = dict()
		for num in arr:
			subseqs[num + difference] = subseqs.get(num, 0) + 1
		return max(subseqs.values())


class Solution:

	def longestSubsequence(self, arr: List[int], difference: int) -> int:
		d = {}
		for a in arr:
			a_ = a - difference
			if difference == 0:
				if a not in d:
					d[a] = 1
				else:
					d[a] = d[a] + 1
			else:
				if a not in d:
					d[a] = 1
				if a - difference in d:
					d[a] = max(d[a], d[a - difference] + 1)
		return max(d.values())


class Solution:

	def longestSubsequence(self, arr: List[int], difference: int) -> int:
		d = {}
		for n in arr:
			d[n] = d.get(n - difference, 0) + 1
		return max(d.values())


class Solution:

	def longestSubsequence(self, arr: List[int], difference: int) -> int:
		dic = {}
		ans = 1
		for x in arr:
			pre = x - difference
			dic[x] = dic.get(pre, 0) + 1
			ans = max(ans, dic[x])
		return max(dic.values())


from collections import defaultdict

class Solution:

	def longestSubsequence(self, arr: List[int], difference: int) -> int:
		mapping = defaultdict(list)
		N = len(arr)
		for i in range(N):
			mapping[arr[i]].append(i)
		dp = [1] * N
		for i in range(1, N):
			curr = arr[i]
			if curr - difference in mapping:
				for idx in mapping[curr - difference]:
					if idx >= i:
						break
					if dp[idx] + 1 > dp[i]:
						dp[i] = dp[idx] + 1
		return max(dp)


class Solution:

	def longestSubsequence(self, arr: List[int], diff: int) -> int:
		mp = {}
		ans = 0
		for n in arr:
			prev = mp.get(n, 0)
			if n - diff in mp:
				mp[n] = mp[n - diff] + 1
			else:
				mp[n] = 1
			mp[n] = max(prev, mp[n])
			ans = max(ans, mp[n])
		return ans


class Solution:

	def longestSubsequence(self, arr: List[int], d: int) -> int:
		mp = {}
		for (i, a) in enumerate(arr):
			if a - d in mp:
				mp[a] = mp[a - d] + 1
			else:
				mp[a] = 1
		return max(mp.values())


from collections import Counter

class Solution:

	def longestSubsequence(self, arr: List[int], difference: int) -> int:
		max_len = 0
		dp = Counter()
		for i in range(len(arr)):
			dp[arr[i]] = max(dp[arr[i] - difference] + 1, dp[arr[i]])
			max_len = max(max_len, dp[arr[i]])
		return max_len


class Solution:

	def longestSubsequence(self, arr: List[int], difference: int) -> int:
		dp = {}
		max_len = 1
		for num in arr:
			dp[num] = max(dp.get(num, 1), 1 + dp.get(num - difference, 0))
			max_len = max(max_len, dp[num])
		return max_len


class Solution:

	def longestSubsequence(self, arr: List[int], diff: int) -> int:
		dp = {}
		for i in arr:
			if i - diff in dp:
				dp[i] = dp[i - diff] + 1
			else:
				dp[i] = 1
		return max(dp.values())


class Solution:

	def longestSubsequence(self, arr: List[int], difference: int) -> int:
		max_len = 1
		dp = {}
		for a in arr:
			if a - difference in dp:
				dp[a] = dp[a - difference] + 1
				max_len = max(max_len, dp[a])
			else:
				dp[a] = 1
		return max_len


class Solution:

	def longestSubsequence(self, arr: List[int], diff: int) -> int:
		d = dict()
		res = 1
		for i in arr:
			if i - diff in d.keys():
				d[i] = 1 + d[i - diff]
			else:
				d[i] = 1
			res = max(res, d[i])
		return res


class Solution:

	def longestSubsequence(self, arr: List[int], difference: int) -> int:
		record = collections.defaultdict(int)
		res = 0
		for (i, v) in enumerate(arr):
			l = 1
			if v - difference in record:
				l = record[v - difference] + 1
			record[v] = l
			res = max(res, l)
		return res


class Solution:

	def longestSubsequence(self, arr: List[int], difference: int) -> int:
		if len(arr) == 1:
			return 1
		d = {arr[0]: 1}
		for i in range(1, len(arr)):
			if arr[i] - difference in d:
				d[arr[i]] = d[arr[i] - difference] + 1
			else:
				d[arr[i]] = 1
		return max(d.values())


class Solution:

	def longestSubsequence(self, arr: List[int], difference: int) -> int:
		_dict = {arr[0]: 1}
		res = 1
		for i in arr[1:]:
			if i - difference in _dict:
				_dict[i] = 1 + _dict[i - difference]
				res = max(res, _dict[i])
			else:
				_dict[i] = 1
		return res


class Solution:

	def longestSubsequence(self, arr: List[int], difference: int) -> int:
		mi = min(arr)
		seq = [0] * (max(arr) - mi + 1)
		m = 0
		for a in arr:
			b = a - difference - mi
			v = 1
			if 0 <= b < len(seq):
				v += seq[b]
				seq[b] = 0
			seq[a - mi] = max(seq[a - mi], v)
			m = max(m, seq[a - mi])
		return m


class Solution:

	def longestSubsequence(self, arr: List[int], difference: int) -> int:
		record = {}
		for i in range(len(arr)):
			a = arr[i]
			if a - difference in record:
				record[a] = record[a - difference] + 1
			else:
				record[a] = 1
		return max(list(record.values()))


class Solution:

	def longestSubsequence(self, arr: List[int], diff: int) -> int:
		d = dict()
		res = 1
		for i in arr:
			t = 0
			try:
				t = d[i - diff]
			except:
				pass
			if t:
				d[i] = 1 + d[i - diff]
			else:
				d[i] = 1
			res = max(res, d[i])
		return res


class Solution:

	def longestSubsequence(self, arr: List[int], difference: int) -> int:
		from collections import defaultdict
		indexMap = defaultdict(list)
		for i in range(len(arr) - 1, -1, -1):
			indexMap[arr[i]].append(i)
		dp = [1] * len(arr)
		maxLen = 1
		for i in range(len(arr)):
			indexMap[arr[i]].pop()
			nextVal = arr[i] + difference
			if nextVal in indexMap and indexMap[nextVal]:
				j = indexMap[nextVal][-1]
				dp[j] = max(dp[i] + 1, dp[j])
				maxLen = max(maxLen, dp[j])
		return maxLen