Given an array A[] of length N. For each index, i (1<=i<=N), find the difference between the number of distinct elements in the left and right side in the of the current element in the array. 
Example 1:
Input:
N = 3
arr[] = {4, 3, 3}
Output: {-1, 0, 2}
Explanation: For index i=1, there are 0 distinct element in the left side of it, and 1 distinct element(3) in it's right side. So difference is 0-1 = -1. 
Similarly for index i=2, there is 1 distinct element (4) in left side of it, and 1 distinct element(3) in it's right side. So difference is 1-1 = 0.
Similarly for index i=3, there are 2 distinct elements (4 and 3) in left side of it, and 0 distinct elements in it's left side. So difference is 2-0 = 2.
Example 2:
Input:
N = 4
arr[] = {4, 4, 3, 3}
Output: {-2, 0, 0, 2}
Explanation: For index i=1, there are 0 distinct element in the left side of it, and 2 distinct element(4 and 3) in it's right side. So difference is 0-2 = -2.
Similarly for index i=2, there is 1 distinct element (4) in left side of it, and 1 distinct element(3) in it's right side. So difference is 1-1 = 0.
Similarly for index i=4, there are 2 distinct elements (4 and 3) in left side of it, and 0 distinct element in it's right side. So difference is 2-0 = 2.
Your Task:  
You don't need to read input or print anything. Your task is to complete the function getDistinctDifference() which takes the array A[] and its size N as input parameters and returns an array containing the difference between number of distinct elements in left and right side for each 1<=i<=N.
Expected Time Complexity: O(N)
Expected Space Complexity: O(N)
Constraints:
1 <= N <= 10^{5}
1 <= A[i] <= 10^{9}
Array may contain duplicate elements.

Source: geeksforgeeks | Difficulty: EASY
Tags: Data structures

Starter code: from typing import List





class Solution:

    def getDistinctDifference(self, N : int, A : List[int]) -> List[int]:

        # code here

        



Solutions:
from typing import List

class Solution:

	def getDistinctDifference(self, N: int, A: List[int]) -> List[int]:
		(dict_, dict_2) = ({}, {})
		(i, j) = (0, N - 1)
		left = [0 for i in range(N)]
		right = [0 for i in range(N)]
		ans = [0 for i in range(N)]
		while i < N and j >= 0:
			right[j] = len(dict_2)
			left[i] = len(dict_)
			if A[i] not in dict_:
				dict_[A[i]] = 1
			if A[j] not in dict_2:
				dict_2[A[j]] = 1
			i += 1
			j -= 1
		for i in range(N):
			ans[i] = left[i] - right[i]
		return ans


from typing import List

class Solution:

	def getDistinctDifference(self, N: int, A: List[int]) -> List[int]:
		newArr = []
		setArr = set()
		dic = {}
		x = len(list(set(A[1:])))
		newArr.append(0 - x)
		setArr.add(A[0])
		for i in range(1, N):
			if A[i] not in dic:
				dic[A[i]] = 1
			else:
				dic[A[i]] += 1
		cnt = len(dic)
		for i in range(1, N - 1):
			if dic[A[i]] == 1:
				cnt -= 1
			else:
				dic[A[i]] -= 1
			newArr.append(len(setArr) - cnt)
			setArr.add(A[i])
		newArr.append(len(setArr))
		return newArr


from typing import List

class Solution:

	def getDistinctDifference(self, N: int, A: List[int]) -> List[int]:
		left = []
		right = []
		a = set()
		b = set()
		for i in A:
			left.append(len(a))
			a.add(i)
		for i in A[::-1]:
			right.append(len(b))
			b.add(i)
		right = right[::-1]
		val = [left[i] - right[i] for i in range(N)]
		return val


from typing import List

class Solution:

	def getDistinctDifference(self, N: int, A: List[int]) -> List[int]:
		(distinct_left, distinct_right) = ([], [0])
		(left, right) = (set(), set())
		res = []
		for index in range(N):
			if index == 0:
				distinct_left.append(0)
			else:
				left.add(A[index - 1])
				distinct_left.append(len(left))
			if index == N - 1:
				continue
			else:
				right.add(A[-index - 1])
				distinct_right.append(len(right))
		for index in range(N):
			res.append(distinct_left[index] - distinct_right[-index - 1])
		return res


from typing import List

class Solution:

	def getDistinctDifference(self, N: int, A: List[int]) -> List[int]:
		ls = set()
		rs = set()
		larr = [-1] * N
		rarr = [-1] * N
		for i in range(N):
			larr[i] = len(ls)
			ls.add(A[i])
		for i in range(N - 1, -1, -1):
			rarr[i] = len(rs)
			rs.add(A[i])
		for i in range(N):
			A[i] = larr[i] - rarr[i]
		return A


from typing import List

class Solution:

	def getDistinctDifference(self, N: int, A: List[int]) -> List[int]:
		le = [0] * N
		ri = [0] * N
		z = []
		s1 = set()
		s2 = set()
		for i in range(N):
			le[i] = len(s1)
			s1.add(A[i])
		for i in range(N - 1, -1, -1):
			ri[i] = len(s2)
			s2.add(A[i])
		for i in range(N):
			z.append(le[i] - ri[i])
		return z


from typing import List

class Solution:

	def getDistinctDifference(self, N: int, A: List[int]) -> List[int]:
		B = set()
		B1 = set()
		C = [0]
		C1 = []
		F = []
		D = []
		A1 = A[::-1].copy()
		for i in range(N):
			B.add(A[i])
			C.append(len(B))
		for i in range(N):
			B1.add(A1[i])
			C1.append(len(B1))
		C1 = C1[::-1]
		C1.append(0)
		for i in range(1, N + 1):
			D.append(C[i - 1] - C1[i])
		return D


from typing import List

class Solution:

	def getDistinctDifference(self, N: int, A: List[int]) -> List[int]:
		st = set()
		l = []
		for i in range(N - 1, -1, -1):
			l.append(len(st))
			st.add(A[i])
		st1 = set()
		ans = []
		for i in range(0, N):
			ans.append(len(st1) - l[N - i - 1])
			st1.add(A[i])
		return ans


from typing import List

class Solution:

	def getDistinctDifference(self, N: int, A: List[int]) -> List[int]:
		set_a = set()
		l_a = 0
		left = [0]
		set_b = set()
		l_b = 0
		right = []
		for i in A:
			if i not in set_a:
				set_a.add(i)
				l_a += 1
			left.append(l_a)
		for i in A[::-1]:
			if i not in set_b:
				set_b.add(i)
				l_b += 1
			right.append(l_b)
		ans = []
		right = right[::-1]
		right.append(0)
		for i in range(1, N + 1):
			ans.append(left[i - 1] - right[i])
		return ans


from typing import List

class Solution:

	def getDistinctDifference(self, N: int, A: List[int]) -> List[int]:
		set_a = set()
		left = [0]
		set_b = set()
		right = []
		for i in A:
			set_a.add(i)
			left.append(len(set_a))
		for i in A[::-1]:
			set_b.add(i)
			right.append(len(set_b))
		ans = []
		right = right[::-1]
		right.append(0)
		for i in range(1, N + 1):
			ans.append(left[i - 1] - right[i])
		return ans


from typing import List

class Solution:

	def getDistinctDifference(self, N: int, A: List[int]) -> List[int]:
		from collections import defaultdict
		st = set()
		l = {}
		for i in range(N):
			l[i] = len(st)
			st.add(A[i])
		st.clear()
		ret = []
		for i in range(N - 1, -1, -1):
			ret.append(l[i] - len(st))
			st.add(A[i])
		return ret[::-1]


from typing import List

class Solution:

	def getDistinctDifference(self, N: int, A: List[int]) -> List[int]:
		st = set()
		left = [0] * N
		right = [0] * N
		for i in range(N):
			left[i] = len(st)
			st.add(A[i])
		st.clear()
		for i in range(N - 1, -1, -1):
			right[i] = len(st)
			st.add(A[i])
		res = [0] * N
		for i in range(N):
			res[i] = left[i] - right[i]
		return res


from typing import List

class Solution:

	def getDistinctDifference(self, N: int, A: List[int]) -> List[int]:
		left = [0 for i in range(N)]
		right = [0 for i in range(N)]
		val_count = set()
		result = []
		for (index, i) in enumerate(A):
			left[index] = len(val_count)
			val_count.add(i)
		val_count = set()
		for (index, i) in enumerate(A[::-1]):
			right[N - 1 - index] = len(val_count)
			val_count.add(i)
		for (value_x, value_y) in zip(left, right):
			result.append(value_x - value_y)
		return result


from typing import List

class Solution:

	def getDistinctDifference(self, n: int, arr: List[int]) -> List[int]:
		if n == 1:
			return [1]
		left = [0] * n
		right = [0] * n
		left[0] = 1
		right[-1] = 1
		s = set()
		s.add(arr[0])
		for i in range(1, n):
			s.add(arr[i])
			left[i] = len(s)
		s.clear()
		s.add(arr[-1])
		for i in range(n - 2, -1, -1):
			s.add(arr[i])
			right[i] = len(s)
		res = [0] * n
		res[0] = -right[1]
		res[-1] = left[-2]
		for i in range(1, n - 1):
			res[i] = left[i - 1] - right[i + 1]
		return res


from typing import List

class Solution:

	def getDistinctDifference(self, N: int, A: List[int]) -> List[int]:
		left = [0] * N
		right = [0] * N
		ans = [0] * N
		leftc = {}
		rightc = {}
		for i in range(N):
			left[i] = len(leftc)
			if A[i] not in leftc:
				leftc[A[i]] = 1
		for i in range(N - 1, -1, -1):
			right[i] = len(rightc)
			if A[i] not in rightc:
				rightc[A[i]] = 1
		for i in range(N):
			ans[i] = left[i] - right[i]
		return ans


from typing import List

class Solution:

	def getDistinctDifference(self, N: int, A: List[int]) -> List[int]:
		(right, left) = (dict(), dict())
		out = [0] * len(A)
		for i in A:
			right[i] = right.get(i, 0) + 1
		uniquesright = len(right)
		for i in range(len(A)):
			right[A[i]] = right[A[i]] - 1
			if right[A[i]] == 0:
				uniquesright -= 1
			out[i] = len(left) - uniquesright
			left[A[i]] = 1
		return out


from typing import List

class Solution:

	def getDistinctDifference(self, N: int, A: List[int]) -> List[int]:
		l = [0 for i in range(N)]
		r = [0 for i in range(N)]
		s = []
		s1 = set()
		s2 = set()
		for i in range(N):
			l[i] = len(s1)
			s1.add(A[i])
		for i in range(N - 1, -1, -1):
			r[i] = len(s2)
			s2.add(A[i])
		for i in range(N):
			s.append(l[i] - r[i])
		return s


from typing import List

class Solution:

	def getDistinctDifference(self, N: int, A: List[int]) -> List[int]:
		setl = set()
		left = [0 for i in range(N)]
		didlr = [0 for i in range(N)]
		i = 0
		while i < N:
			left[i] = len(setl)
			setl.add(A[i])
			i += 1
		i = N - 1
		setl = set()
		while i > -1:
			didlr[i] = left[i] - len(setl)
			setl.add(A[i])
			i -= 1
		return didlr


from typing import List
from typing import List

class Solution:

	def getDistinctDifference(self, N: int, A: List[int]) -> List[int]:
		i = 0
		j = 0
		k = 0
		l = 0
		res = []
		res_b = []
		s1 = set([])
		s2 = set([])
		k = len(A) - 1
		for i in A:
			res.append(len(s2))
			res_b.append(len(s1))
			s2.add(i)
			s1.add(A[k])
			k = k - 1
		res_b.reverse()
		for i in range(0, len(A)):
			res[i] = res[i] - res_b[i]
		return res
		return res


from typing import List

class Solution:

	def getDistinctDifference(self, N: int, A: List[int]) -> List[int]:
		leftMap = {}
		rightMap = {}
		for i in range(N):
			if A[i] in rightMap:
				rightMap[A[i]] += 1
			else:
				rightMap[A[i]] = 1
		res = []
		for i in range(N):
			countLeft = len(leftMap)
			if rightMap[A[i]] > 1:
				rightMap[A[i]] -= 1
			else:
				del rightMap[A[i]]
			countRight = len(rightMap)
			res.append(countLeft - countRight)
			if A[i] in leftMap:
				leftMap[A[i]] += 1
			else:
				leftMap[A[i]] = 1
		return res


from typing import List

class Solution:

	def getDistinctDifference(self, N: int, A: List[int]) -> List[int]:
		left = [0 for i in range(N)]
		se = set()
		for i in range(1, N):
			se.add(A[i - 1])
			left[i] = len(se)
		diff = [0 for i in range(N)]
		se = set()
		for i in range(N - 2, -1, -1):
			se.add(A[i + 1])
			diff[i] = left[i] - len(se)
		diff[-1] = left[-1]
		return diff


from typing import List

class Solution:

	def getDistinctDifference(self, N: int, A: List[int]) -> List[int]:
		distinct = set()
		diff = [0] * N
		for i in range(N):
			diff[i] += len(distinct)
			distinct.add(A[i])
		distinct.clear()
		for i in range(N - 1, -1, -1):
			diff[i] -= len(distinct)
			distinct.add(A[i])
		return diff


from typing import List

class Solution:

	def getDistinctDifference(self, N: int, A: List[int]) -> List[int]:
		leftDistinct = [0 for _ in range(N)]
		rightDistinct = [0 for _ in range(N)]
		s = set()
		s.add(A[0])
		for i in range(1, N):
			leftDistinct[i] = len(s)
			s.add(A[i])
		s.clear()
		s.add(A[N - 1])
		for i in reversed(range(N - 1)):
			rightDistinct[i] = len(s)
			s.add(A[i])
		result = []
		for i in range(N):
			result.append(leftDistinct[i] - rightDistinct[i])
		return result


from typing import List

class Solution:

	def getDistinctDifference(self, N: int, A: List[int]) -> List[int]:
		a = set()
		l = [0] * N
		r = [0] * N
		for i in range(N):
			l[i] = len(a)
			a.add(A[i])
		a.clear()
		for i in range(N - 1, -1, -1):
			r[i] = len(a)
			a.add(A[i])
		res = [0] * N
		for i in range(N):
			res[i] = l[i] - r[i]
		return res


from typing import List

class Solution:

	def getDistinctDifference(self, N: int, arr: List[int]) -> List[int]:
		s = set()
		left = [0] * N
		right = [0] * N
		s.add(arr[0])
		cnt = 1
		for i in range(1, N):
			left[i] = cnt
			if arr[i] not in s:
				cnt += 1
				s.add(arr[i])
		s.clear()
		cnt = 1
		s.add(arr[N - 1])
		for i in range(N - 2, -1, -1):
			right[i] = cnt
			if arr[i] not in s:
				cnt += 1
				s.add(arr[i])
		ans = [0] * N
		for i in range(0, N):
			ans[i] = left[i] - right[i]
		return ans


from typing import List

class Solution:

	def getDistinctDifference(self, N: int, A: List[int]) -> List[int]:
		if N == 0:
			return []
		if N == 1:
			return [0]
		if N == 2:
			return [-1, -1]
		l = [0] * N
		r = [0] * N
		ls = set()
		rs = set()
		for i in range(N):
			l[i] = len(ls)
			ls.add(A[i])
		for i in range(N - 1, -1, -1):
			r[i] = len(rs)
			rs.add(A[i])
		for i in range(N):
			l[i] = l[i] - r[i]
		return l


from typing import List

class Solution:

	def getDistinctDifference(self, N: int, A: List[int]) -> List[int]:
		left = set()
		right = set()
		(l, r) = ([0 for i in range(N)], [0 for i in range(N)])
		for i in range(N):
			l[i] = len(left)
			r[N - 1 - i] = len(right)
			left.add(A[i])
			right.add(A[N - 1 - i])
		dif = [0 for _ in range(N)]
		for i in range(N):
			dif[i] = l[i] - r[i]
		return dif


from typing import List

class Solution:

	def getDistinctDifference(self, N: int, A: List[int]) -> List[int]:
		pref = []
		suff = []
		st = set()
		for i in range(N):
			st.add(A[i])
			pref.append(len(st))
		st = set()
		for i in range(N - 1, -1, -1):
			st.add(A[i])
			suff.append(len(st))
		suff = suff[::-1]
		ans = [-suff[1]]
		for i in range(1, N - 1):
			ans.append(pref[i - 1] - suff[i + 1])
		ans.append(pref[N - 2])
		return ans


from typing import List

class Solution:

	def getDistinctDifference(self, N: int, A: List[int]) -> List[int]:
		left = [-1] * N
		right = [-1] * N
		ele = set()
		left[0] = 0
		ele.add(A[0])
		flag = True
		for i in range(1, N):
			left[i] = left[i - 1]
			if flag:
				left[i] += 1
			flag = False
			if A[i] not in ele:
				flag = True
				ele.add(A[i])
		ele.clear()
		right[-1] = 0
		ele.add(A[-1])
		flag = True
		for i in range(N - 2, -1, -1):
			right[i] = right[i + 1]
			if flag:
				right[i] += 1
			flag = False
			if A[i] not in ele:
				flag = True
				ele.add(A[i])
		ans = []
		for i in range(N):
			ans.append(left[i] - right[i])
		return ans


from typing import List

class Solution:

	def getDistinctDifference(self, N: int, A: List[int]) -> List[int]:
		i = 0
		j = N - 1
		ans = [0] * N
		c1 = 0
		c2 = 0
		left = [0] * N
		right = [0] * N
		visited1 = {}
		visited2 = {}
		while i < N and j >= 0:
			left[i] = len(visited1)
			right[j] = len(visited2)
			if A[i] not in visited1:
				visited1[A[i]] = 1
			if A[j] not in visited2:
				visited2[A[j]] = 1
			i += 1
			j -= 1
		for i in range(N):
			ans[i] = left[i] - right[i]
		return ans


from typing import List

class Solution:

	def getDistinctDifference(self, N: int, A: List[int]) -> List[int]:
		ans = []
		rightdict = {}
		leftdict = {}
		for i in A:
			rightdict[i] = 0
		for i in A:
			rightdict[i] += 1
		for i in A:
			rightdict[i] = rightdict[i] - 1
			if rightdict[i] == 0:
				del rightdict[i]
			ans1 = len(leftdict.keys()) - len(rightdict.keys())
			ans.append(ans1)
			if i in leftdict:
				leftdict[i] += 1
			else:
				leftdict[i] = 1
		return ans


from typing import List

class Solution:

	def getDistinctDifference(self, N: int, A: List[int]) -> List[int]:
		s = set()
		a = []
		a1 = []
		ans = []
		for i in range(N):
			a.append(len(s))
			s.add(A[i])
		s.clear()
		A = A[::-1]
		for i in range(N):
			a1.append(len(s))
			s.add(A[i])
		a1 = a1[::-1]
		for i in range(N):
			ans.append(a[i] - a1[i])
		return ans


from typing import List

class Solution:

	def getDistinctDifference(self, N: int, A: List[int]) -> List[int]:
		st = set()
		ans_1 = []
		ans_2 = []
		ans = []
		for i in range(N):
			ans_1.append(len(st))
			st.add(A[i])
		st.clear()
		A = A[::-1]
		for i in range(N):
			ans_2.append(len(st))
			st.add(A[i])
		ans_2 = ans_2[::-1]
		for i in range(N):
			ans.append(ans_1[i] - ans_2[i])
		return ans


from typing import List

class Solution:

	def getDistinctDifference(self, N: int, A: List[int]) -> List[int]:
		r = {}
		l = {}
		for n in A:
			r[n] = r.get(n, 0) + 1
		res = []
		for n in A:
			r[n] -= 1
			if r[n] == 0:
				del r[n]
			res.append(len(l) - len(r))
			l[n] = l.get(n, 0) + 1
		return res


from typing import List

class Solution:

	def getDistinctDifference(self, N: int, A: List[int]) -> List[int]:
		left = [-1] * N
		right = [-1] * N
		lst = set()
		rst = set()
		ans = []
		lst.add(A[0])
		rst.add(A[-1])
		left[0] = 0
		right[-1] = 0
		for i in range(1, N):
			left[i] = len(lst)
			lst.add(A[i])
		for i in range(N - 2, -1, -1):
			right[i] = len(rst)
			rst.add(A[i])
		for i in range(N):
			ans.append(left[i] - right[i])
		return ans


from typing import List

class Solution:

	def getDistinctDifference(self, N: int, A: List[int]) -> List[int]:
		B = []
		S = set()
		left = []
		for i in range(N):
			left.append(len(S))
			S.add(A[i])
		S = set()
		for i in range(N - 1, -1, -1):
			B.append(left[i] - len(S))
			S.add(A[i])
		return B[::-1]


from typing import List

class Solution:

	def getDistinctDifference(self, N: int, A: List[int]) -> List[int]:
		s = set()
		res = [0 for i in range(N)]
		c = 0
		for i in range(1, N):
			if A[i - 1] not in s:
				c += 1
				s.add(A[i - 1])
			res[i] = -1 * c
		s = set()
		c = 0
		for i in range(N - 2, -1, -1):
			if A[i + 1] not in s:
				c += 1
				s.add(A[i + 1])
			res[i] = res[i] + c
		for i in range(N):
			res[i] = res[i] * -1
		return res


from typing import List

class Solution:

	def getDistinctDifference(self, N: int, A: List[int]) -> List[int]:
		hl = []
		hr = []
		s = set()
		s.add(A[0])
		hl.append(0)
		for i in range(1, N):
			hl.append(len(s))
			s.add(A[i])
		hr.append(0)
		s = set()
		s.add(A[-1])
		for i in range(N - 2, -1, -1):
			hr.append(len(s))
			s.add(A[i])
		hr = hr[::-1]
		ans = []
		for i in range(N):
			ans.append(hl[i] - hr[i])
		return ans


from typing import List

class Solution:

	def getDistinctDifference(self, N: int, A: List[int]) -> List[int]:
		ans = [0] * N
		if N == 1:
			return ans
		left = [0] * N
		right = [0] * N
		left[1] = 1
		right[N - 2] = 1
		lmp = {}
		rmp = {}
		for i in range(N):
			lmp[A[i]] = 0
			rmp[A[i]] = 0
		lmp[A[0]] = 1
		rmp[A[N - 1]] = 1
		for i in range(2, N):
			if lmp[A[i - 1]] == 0:
				left[i] = left[i - 1] + 1
				lmp[A[i - 1]] = 1
			else:
				left[i] = left[i - 1]
		for i in range(N - 3, -1, -1):
			if rmp[A[i + 1]] == 0:
				right[i] = right[i + 1] + 1
				rmp[A[i + 1]] = 1
			else:
				right[i] = right[i + 1]
		for i in range(N):
			ans[i] = left[i] - right[i]
		return ans


from typing import List

class Solution:

	def getDistinctDifference(self, N: int, A: List[int]) -> List[int]:
		m = {}
		l = []
		r = []
		cnt = 0
		for x in range(N):
			if A[x] not in m:
				m[A[x]] = True
				cnt += 1
				l.append(cnt)
			else:
				l.append(cnt)
		m = {}
		cnt = 0
		for x in reversed(range(N)):
			if A[x] not in m:
				m[A[x]] = True
				cnt += 1
				r.append(cnt)
			else:
				r.append(cnt)
		r.reverse()
		out = []
		for x in range(N):
			lc = 0
			rc = 0
			if x - 1 >= 0:
				lc = l[x - 1]
			if x + 1 < N:
				rc = r[x + 1]
			out.append(lc - rc)
		return out


from typing import List

class Solution:

	def getDistinctDifference(self, N: int, A: List[int]) -> List[int]:
		left = {}
		right = {}
		ans = []
		lCount = rCount = 0
		for i in A:
			if i not in right:
				right[i] = 1
				rCount += 1
			else:
				right[i] += 1
		for i in A:
			right[i] -= 1
			if right[i] == 0:
				rCount -= 1
			ans.append(lCount - rCount)
			if i not in left:
				left[i] = 1
				lCount += 1
			else:
				left[i] += 1
		return ans


from typing import List

class Solution:

	def getDistinctDifference(self, N: int, A: List[int]) -> List[int]:
		d = {}
		s = set()
		for i in A:
			if i not in d:
				d[i] = 1
			else:
				d[i] += 1
		e = [0] * N
		s.add(A[-1])
		d[A[-1]] -= 1
		if d[A[-1]] == 0:
			del d[A[-1]]
		e[-1] = len(d)
		for i in range(N - 2, -1, -1):
			d[A[i]] -= 1
			if d[A[i]] == 0:
				del d[A[i]]
			e[i] = len(d) - len(s)
			s.add(A[i])
		return e


from typing import List

class Solution:

	def getDistinctDifference(self, N: int, arr: List[int]) -> List[int]:
		left_prefix_arr = []
		right_prefix_arr = [-1] * N
		buff = set()
		count = 0
		for (i, each) in enumerate(arr):
			left_prefix_arr.append(count)
			if each not in buff:
				buff.add(each)
				count += 1
		count = 0
		idx = N - 1
		buff = set()
		for i in reversed(range(N)):
			right_prefix_arr[idx] = count
			idx -= 1
			if arr[i] not in buff:
				buff.add(arr[i])
				count += 1
		res = []
		for i in range(N):
			res.append(left_prefix_arr[i] - right_prefix_arr[i])
		return res


from typing import List

class Solution:

	def getDistinctDifference(self, N: int, A: List[int]) -> List[int]:
		d1 = {}
		d2 = {}
		(i, j) = (0, N - 1)
		l = [0 for i in range(N)]
		r = [0 for i in range(N)]
		ans = [0 for i in range(N)]
		while i < N and j >= 0:
			r[j] = len(d2)
			l[i] = len(d1)
			if A[i] not in d1:
				d1[A[i]] = 1
			if A[j] not in d2:
				d2[A[j]] = 1
			i += 1
			j -= 1
		for i in range(N):
			ans[i] = l[i] - r[i]
		return ans


from typing import List

class Solution:

	def getDistinctDifference(self, N: int, A: List[int]) -> List[int]:
		result = []
		leftDistinct = set()
		rightDistinct = set(A)
		rightDict = dict.fromkeys(rightDistinct, 0)
		for i in A:
			rightDict[i] += 1
		for i in A:
			rightDict[i] -= 1
			if rightDict[i] == 0:
				rightDistinct.remove(i)
			result.append(len(leftDistinct) - len(rightDistinct))
			leftDistinct.add(i)
		return result


from typing import List

class Solution:

	def getDistinctDifference(self, N: int, A: List[int]) -> List[int]:
		set1 = {}
		set2 = {}
		for i in A:
			if i in set2:
				set2[i] += 1
			else:
				set2[i] = 1
		res = []
		for i in range(N):
			leftcount = len(set1)
			if set2[A[i]] > 1:
				set2[A[i]] -= 1
			else:
				del set2[A[i]]
			res.append(leftcount - len(set2))
			if A[i] in set1:
				set1[A[i]] += 1
			else:
				set1[A[i]] = 1
		return res


from typing import List

class Solution:

	def getDistinctDifference(self, n: int, arr: List[int]) -> List[int]:
		left = [0 for i in range(n + 1)]
		right = [0 for i in range(n + 1)]
		d = dict()
		for i in range(n):
			left[i] = left[i - 1]
			if arr[i] not in d:
				left[i] += 1
			d[arr[i]] = 1
		d = dict()
		for i in range(n - 1, -1, -1):
			right[i] = right[i + 1]
			if arr[i] not in d:
				right[i] += 1
			d[arr[i]] = 1
		ans = [left[i - 1] - right[i + 1] for i in range(n)]
		return ans


from typing import List

class Solution:

	def getDistinctDifference(self, N: int, A: List[int]) -> List[int]:
		st = set()
		left = [0] * N
		right = [0] * N
		for i in range(N):
			left[i] = len(st)
			st.add(A[i])
		st.clear()
		for i in range(N - 1, -1, -1):
			right[i] = len(st)
			st.add(A[i])
		res = [0] * N
		for i in range(N):
			res[i] = left[i] - right[i]
		return res

	def getDistinctDifference_v2(self, N: int, A: List[int]) -> List[int]:
		left = [0] * N
		right = [0] * N
		ans = [0] * N
		if N <= 3:
			if N == 1:
				return [0]
			if N == 2:
				return [-1, 1]
			if A[1] == A[2]:
				return [-1, 0, 2]
			else:
				return [-2, 0, 2]
		left[0] = 0
		left[1] = 1
		right[N - 1] = 0
		right[N - 2] = 1
		for i in range(N):
			fr = {}
			for j in range(N):
				if A[j] in fr:
					fr[A[j]][0] += 1
				else:
					fr[A[j]] = [1, 0, 0]
		rn = len(fr)
		for i in range(0, N - 2):
			fr[A[i]][1] += 1
			if fr[A[i]][1] == fr[A[i]][0]:
				rn -= 1
			right[i] = rn
		rn = len(fr)
		for i in range(N - 1, 1, -1):
			fr[A[i]][2] += 1
			if fr[A[i]][2] == fr[A[i]][0]:
				rn -= 1
			left[i] = rn
			ans[i] = left[i] - right[i]
		ans[0] = left[0] - right[0]
		ans[1] = left[1] - right[1]
		return ans

	def getDistinctDifference_v1(self, N: int, A: List[int]) -> List[int]:
		left = [0] * N
		right = [0] * N
		if N <= 3:
			if N == 1:
				return [0]
			if N == 2:
				return [-1, 1]
			if A[1] == A[2]:
				return [-1, 0, 2]
			else:
				return [-2, 0, 2]
		left[0] = 0
		left[1] = 1
		right[N - 1] = 0
		right[N - 2] = 1
		for i in range(N):
			ur = {}
			ul = {}
			if i < N - 2:
				for j in range(i + 1, N):
					if A[j] not in ur:
						right[i] += 1
						ur[A[j]] = 1
			if i >= 2:
				for j in range(i - 1, -1, -1):
					if A[j] not in ul:
						left[i] += 1
						ul[A[j]] = 1
		ans = []
		for j in range(N):
			ans.append(left[j] - right[j])
		return ans


from typing import List

class Solution:

	def getDistinctDifference(self, N: int, a: List[int]) -> List[int]:
		mp = {}
		mp2 = {}
		ans = []
		for i in range(N):
			mp[a[i]] = mp.get(a[i], 0) + 1
		for i in range(N):
			mp[a[i]] -= 1
			if mp[a[i]] == 0:
				del mp[a[i]]
			ans.append(len(mp2) - len(mp))
			mp2[a[i]] = mp2.get(a[i], 0) + 1
		return ans


from typing import List

class Solution:

	def getDistinctDifference(self, N: int, A: List[int]) -> List[int]:
		returningList = []
		left = set()
		right = set()
		dicDa = {}
		dicDar = {}
		B = A[::-1]
		for i in range(N):
			dicDa[i] = len(left)
			dicDar[i] = len(right)
			left.add(A[i])
			right.add(B[i])
		for i in range(N):
			returningList.append(dicDa[i] - dicDar[N - i - 1])
		return returningList


from typing import List

class Solution:

	def getDistinctDifference(self, N: int, A: List[int]) -> List[int]:
		d = {}
		res = []
		for i in A:
			res.append(len(d))
			d[i] = 1
		c = {}
		for i in range(N - 1, -1, -1):
			res[i] -= len(c)
			c[A[i]] = 1
		return res


from typing import List

class Solution:

	def getDistinctDifference(self, N: int, A: List[int]) -> List[int]:
		ans = []
		right_count_uniq = []
		left_count_uniq = []
		appeared_nums = set()
		c = 0
		for i in A:
			left_count_uniq.append(c)
			if i not in appeared_nums:
				c += 1
				appeared_nums.add(i)
		appeared_nums = set()
		c = 0
		for i in range(len(A) - 1, -1, -1):
			right_count_uniq.append(c)
			if A[i] not in appeared_nums:
				c += 1
				appeared_nums.add(A[i])
		for i in range(len(A)):
			ans.append(left_count_uniq[i] - right_count_uniq[len(A) - 1 - i])
		return ans


from typing import List

class Solution:

	def getDistinctDifference(self, N: int, A: List[int]) -> List[int]:
		arr = [0 for _ in range(N)]
		arr1 = [0 for _ in range(N)]
		s = set()
		for i in range(N):
			arr[i] = len(s)
			s.add(A[i])
		s.clear()
		for i in range(N - 1, -1, -1):
			arr1[i] = len(s)
			s.add(A[i])
		ans = []
		for i in range(N):
			ans.append(arr[i] - arr1[i])
		return ans


from typing import List

class Solution:

	def getDistinctDifference(self, N: int, A: List[int]) -> List[int]:
		(l, r) = (dict(), dict())
		for x in A:
			r[x] = r.get(x, 0) + 1
		ans = []
		for x in A:
			if r.get(x) == 1:
				ans.append(len(l) - len(r) + 1)
			else:
				ans.append(len(l) - len(r))
			l[x] = l.get(x, 0) + 1
			r[x] -= 1
			if r[x] == 0:
				del r[x]
		return ans