Given an array arr[] of n integers. Count the total number of sub-array having total distinct elements same as that of total distinct elements of the original array.
 
Example 1:
Input:
N=5
arr[] = {2, 1, 3, 2, 3} 
Output: 5
Explanation:
Total distinct elements in array is 3
Total sub-arrays that satisfy the condition
are:
Subarray from index 0 to 2
Subarray from index 0 to 3
Subarray from index 0 to 4
Subarray from index 1 to 3
Subarray from index 1 to 4
Example 2:
Input:
N=5
arr[] = {2, 4, 4, 2, 4} 
Output: 9
Your Task:
Since, this is a function problem. You don't need to take any input, as it is already accomplished by the driver code. You just need to complete the function countDistinctSubarray() that takes array arr and integer n  as parameters and returns the desired result.
 
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(N).
 
Constraints:
1 ≤ N ≤ 10^{4}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: String algorithms

Data structures

Amortized analysis

Starter code: #User function Template for python3



class Solution:

    def countDistinctSubarray(self,arr, n): 

        #code here.

Solutions:
class Solution:

	def countDistinctSubarray(self, arr, n):
		uniq = 0
		(dt, ds) = ({}, {})
		for i in range(n):
			if dt.get(arr[i], 0) == 0:
				uniq += 1
			dt[arr[i]] = 1
		start = end = ans = 0
		cnt = 0
		for i in range(n):
			if ds.get(arr[i], 0) == 0:
				cnt += 1
			ds[arr[i]] = ds.get(arr[i], 0) + 1
			if cnt == uniq:
				end = i
				break
		while end < n:
			if start < n and ds[arr[start]] >= dt[arr[start]] and (cnt == uniq):
				if ds[arr[start]] == dt[arr[start]]:
					cnt -= 1
				ans += n - end
				ds[arr[start]] -= 1
				start += 1
			else:
				end += 1
				if end < n:
					ds[arr[end]] = ds.get(arr[end], 0) + 1
					if ds[arr[end]] == dt[arr[end]]:
						cnt += 1
		return ans


import collections

class Solution:

	def countDistinctSubarray(self, nums, n):
		k = len(set(nums))

		def count_k(k):
			hashmp = collections.defaultdict(int)
			(l, r) = (0, 0)
			cnt = 0
			ans = 0
			while r < n:
				hashmp[nums[r]] += 1
				if hashmp[nums[r]] == 1:
					cnt += 1
				while cnt > k:
					hashmp[nums[l]] -= 1
					if not hashmp[nums[l]]:
						cnt -= 1
					l += 1
				ans += r - l + 1
				r += 1
			return ans
		return count_k(k) - count_k(k - 1)


import collections

class Solution:

	def countDistinctSubarray(self, nums, n):
		k = len(list(set(nums)))

		def check(k):
			(l, r) = (0, 0)
			tans = 0
			d = collections.defaultdict(int)
			c = 0
			while r < n:
				if nums[r] not in d:
					c = 0
					d[nums[r]] = 1
				else:
					d[nums[r]] += 1
				while len(d) > k:
					d[nums[l]] -= 1
					if d[nums[l]] == 0:
						del d[nums[l]]
					l += 1
				tans += r - l + 1
				r += 1
			return tans
		return check(k) - check(k - 1)


class Solution:

	def countDistinctSubarray(self, arr, n):
		tot = len(set(arr))
		(fp, sp, mp) = (0, 0, {})
		ans = 0
		while sp < n:
			if arr[sp] in mp:
				mp[arr[sp]] += 1
			else:
				mp[arr[sp]] = 1
			while len(mp) == tot and fp <= sp:
				ans += n - sp
				mp[arr[fp]] -= 1
				if mp[arr[fp]] == 0:
					mp.pop(arr[fp])
				fp += 1
			sp += 1
		return ans


class Solution:

	def countDistinctSubarray(self, arr, n):
		distinctEle = len(set(arr))
		i = 0
		j = 0
		ans = 0
		dic = {}
		currDistinctEle = 0
		cnt = 0
		while j < n:
			while i < n and currDistinctEle == distinctEle:
				ans += n - j + 1
				dic[arr[i]] -= 1
				if dic[arr[i]] == 0:
					del dic[arr[i]]
					currDistinctEle -= 1
				i += 1
			if arr[j] not in dic:
				dic[arr[j]] = 1
				currDistinctEle += 1
			else:
				dic[arr[j]] += 1
			j += 1
		while i < n and currDistinctEle == distinctEle:
			ans += n - j + 1
			dic[arr[i]] -= 1
			if dic[arr[i]] == 0:
				del dic[arr[i]]
				currDistinctEle -= 1
			i += 1
		return ans


class Solution:

	def countDistinctSubarray(self, a, n):
		d = {}
		k = 0
		for i in range(n):
			if a[i] not in d.keys():
				d[a[i]] = 1
				k += 1
		ans = 0
		i = 0
		d = {}
		while i in range(n):
			if a[i] not in d.keys():
				d[a[i]] = 1
			else:
				d[a[i]] += 1
			if len(d) == k:
				j = 0
				cnt = 1
				while d[a[j]] != 1:
					cnt += 1
					d[a[j]] -= 1
					j += 1
				ans += cnt
				break
			i += 1
		i = i + 1
		while i < n:
			d[a[i]] += 1
			while d[a[j]] != 1:
				cnt += 1
				d[a[j]] -= 1
				j += 1
			ans += cnt
			i += 1
		return ans


class Solution:

	def solve(self, arr, k, n):
		d = {}
		(count, l, r) = (0, 0, 0)
		while r < n:
			if arr[r] not in d:
				d[arr[r]] = 0
			d[arr[r]] += 1
			while len(d) > k:
				if arr[l] not in d:
					d[arr[l]] = 0
				d[arr[l]] -= 1
				if d[arr[l]] <= 0:
					del d[arr[l]]
				l += 1
			count += r - l + 1
			r += 1
		return count

	def countDistinctSubarray(self, arr, n):
		d = {}
		for i in arr:
			d[i] = d.get(i, 0) + 1
		k = len(d)
		return self.solve(arr, k, n) - self.solve(arr, k - 1, n)


class Solution:

	def countDistinctSubarray(self, arr, n):
		count = set(arr)
		dic = dict()
		(i, j) = (0, 0)
		ans = 0
		while j < n:
			if arr[j] in dic:
				dic[arr[j]] += 1
			else:
				dic[arr[j]] = 1
			while len(dic) == len(count):
				ans += n - j
				dic[arr[i]] -= 1
				if dic[arr[i]] == 0:
					del dic[arr[i]]
				i += 1
			j += 1
		return ans


from collections import defaultdict

class Solution:

	def countDistinctSubarray(self, arr, n):
		store = defaultdict(lambda : 0)
		m = len(set(arr))
		count = 0
		i = 0
		j = 0
		for item in arr:
			while i < n and len(store) < m:
				store[arr[i]] += 1
				i += 1
			while j < n and arr[j] in store:
				j += 1
			if len(store) == m:
				count += j - i + 1
			store[item] -= 1
			if store[item] == 0:
				del store[item]
		return count


class Solution:

	def countDistinctSubarray(self, arr, n):
		s = set(arr)
		k = len(s)
		d = {}
		s = 0
		count = 0
		for i in range(n):
			d[arr[i]] = d.get(arr[i], 0) + 1
			while len(d) >= k and s <= i:
				count += n - i
				d[arr[s]] -= 1
				if d[arr[s]] == 0:
					d.pop(arr[s])
				s += 1
		return count


class Solution:

	def countDistinctSubarray(self, arr, n):
		d = {}
		for i in range(len(arr)):
			if arr[i] in d:
				d[arr[i]] = d[arr[i]] + 1
			else:
				d[arr[i]] = 1
		i = 0
		j = 0
		re = 0
		d1 = {}
		while j < len(arr):
			if arr[j] in d1:
				d1[arr[j]] = d1[arr[j]] + 1
			else:
				d1[arr[j]] = 1
			if len(d1) < len(d):
				j = j + 1
			elif len(d1) == len(d):
				while len(d1) == len(d):
					result = len(arr) - j
					re = re + result
					d1[arr[i]] = d1[arr[i]] - 1
					if d1[arr[i]] == 0:
						del d1[arr[i]]
					i = i + 1
				j = j + 1
		return re


class Solution:

	def countDistinctSubarray(self, arr, n):
		d = {}
		l = len(set(arr))
		st = 0
		ans = 0
		for i in range(n):
			if arr[i] in d:
				d[arr[i]] += 1
			else:
				d[arr[i]] = 1
			while len(d) == l:
				ans += n - i
				d[arr[st]] -= 1
				if d[arr[st]] == 0:
					del d[arr[st]]
				st += 1
		return ans


class Solution:

	def countDistinctSubarray(self, nums, n):
		k = len(set(nums))
		return self.subarraysWithatmostkDistinct(nums, k) - self.subarraysWithatmostkDistinct(nums, k - 1)

	def subarraysWithatmostkDistinct(self, nums, k):
		memo = {}
		Count = release = 0
		for acquire in range(len(nums)):
			if nums[acquire] in memo:
				memo[nums[acquire]] += 1
			else:
				memo[nums[acquire]] = 1
			while release <= acquire and len(memo) > k:
				memo[nums[release]] -= 1
				if memo[nums[release]] == 0:
					del memo[nums[release]]
				release += 1
			Count += acquire - release + 1
		return Count


import collections

class Solution:

	def countDistinctSubarray(self, arr, n):
		l = 0
		r = 0
		res = 0
		map1 = collections.defaultdict(int)
		map2 = collections.defaultdict(int)
		for n in arr:
			map1[n] += 1
		nums = arr
		while r < len(nums):
			map2[nums[r]] += 1
			r += 1
			if len(map2) == len(map1):
				a = 0
				while l < len(nums) and len(map2) == len(map1):
					a += 1
					map2[nums[l]] -= 1
					if map2[nums[l]] == 0:
						del map2[nums[l]]
					l += 1
				res += a * (len(nums) - r + 1)
		return res


class Solution:

	def countDistinctSubarray(self, arr, n):

		def subs(arr, n, maxdistinct):
			hm = {}
			dist_cnt = 0
			(start, end) = (0, 0)
			subs = 0
			while end < n:
				hm[arr[end]] = 1 + hm.get(arr[end], 0)
				if hm[arr[end]] == 1:
					dist_cnt += 1
				while dist_cnt > maxdistinct:
					hm[arr[start]] -= 1
					if hm[arr[start]] == 0:
						dist_cnt -= 1
					start += 1
				subs += end - start + 1
				end += 1
			return subs
		s = set(arr)
		k = len(s)
		atmostk = subs(arr, n, k)
		atmostk_1 = subs(arr, n, k - 1)
		return atmostk - atmostk_1


from collections import deque

class Solution:

	def countDistinctSubarray(self, s, n):
		d = {}
		ans = 0
		k = len(set(s))
		start = 0
		for i in range(n):
			d[s[i]] = d.get(s[i], 0) + 1
			while len(d) >= k and start <= i:
				ans += n - i
				d[s[start]] -= 1
				if d[s[start]] == 0:
					del d[s[start]]
				start += 1
		return ans


class Solution:

	def countDistinctSubarray(self, arr, n):
		s = set()
		for x in arr:
			s.add(x)
		i = -1
		j = -1
		count = 0
		d = {}
		while True:
			f1 = False
			f2 = False
			while i < len(arr) - 1:
				f1 = True
				i += 1
				try:
					d[arr[i]] += 1
				except:
					d[arr[i]] = 1
				if len(d) == len(s):
					count += len(arr) - i
					break
			while j < i:
				j += 1
				f2 = True
				if d[arr[j]] == 1:
					d.pop(arr[j])
				else:
					d[arr[j]] -= 1
				if len(d) == len(s):
					count += len(arr) - i
				else:
					break
			if f1 == False and f2 == False:
				return count


from collections import defaultdict

class Solution:

	def countDistinctSubarray(self, arr, n):
		dis = len(set(arr))
		c = 0
		start = 0
		ans = 0
		dic = defaultdict(lambda : 0)
		for i in range(n):
			if dic[arr[i]] == 0:
				c += 1
			dic[arr[i]] += 1
			if c == dis:
				ans += n - i
				while dic[arr[start]] >= 1:
					dic[arr[start]] -= 1
					if dic[arr[start]] == 0:
						c -= 1
						start += 1
						break
					start += 1
					ans += n - i
		return ans


class Solution:

	def countDistinctSubarray(self, arr, n):
		d = {}
		l = len(set(arr))
		tot = 0
		res = 0
		for i in range(n):
			if arr[i] in d:
				d[arr[i]] += 1
			else:
				d[arr[i]] = 1
			while len(d) == l:
				res += n - i
				d[arr[tot]] -= 1
				if d[arr[tot]] == 0:
					del d[arr[tot]]
				tot += 1
		return res


class Solution:

	def countDistinctSubarray(self, arr, n):
		vis = dict()
		for i in range(n):
			vis[arr[i]] = 1
		k = len(vis)
		vid = dict()
		ans = 0
		right = 0
		window = 0
		for left in range(n):
			while right < n and window < k:
				if arr[right] in vid.keys():
					vid[arr[right]] += 1
				else:
					vid[arr[right]] = 1
				if vid[arr[right]] == 1:
					window += 1
				right += 1
			if window == k:
				ans += n - right + 1
			vid[arr[left]] -= 1
			if vid[arr[left]] == 0:
				window -= 1
		return ans


class Solution:

	def countDistinctSubarray(self, arr, n):
		ans = 0
		target_length = len(set(arr))
		d = {}
		length = 0
		left = 0
		for i in range(n):
			if arr[i] not in d or d[arr[i]] == 0:
				length += 1
				d[arr[i]] = 1
			else:
				d[arr[i]] += 1
			while length == target_length:
				ans += n - i
				d[arr[left]] -= 1
				if d[arr[left]] == 0:
					length -= 1
				left += 1
		return ans


class Solution:

	def countDistinctSubarray(self, arr, n):
		t = len(set(arr))
		ans = 0
		left = 0
		d = {}
		for i in range(n):
			if arr[i] not in d:
				d[arr[i]] = 1
			else:
				d[arr[i]] += 1
			while len(d) == t:
				ans += n - i
				d[arr[left]] -= 1
				if d[arr[left]] == 0:
					del d[arr[left]]
				left += 1
		return ans


class Solution:

	def countDistinctSubarray(self, arr, n):
		hash_arr = {}
		k = 0
		for num in arr:
			if num not in hash_arr:
				k += 1
				hash_arr[num] = 1
			else:
				hash_arr[num] += 1
		hash_arr = {}
		match_cnt = 0
		i = -1
		j = -1
		ans = 0
		while True:
			f1 = False
			f2 = False
			while j < n - 1 and match_cnt < k:
				j += 1
				if arr[j] not in hash_arr:
					hash_arr[arr[j]] = 1
					match_cnt += 1
				else:
					hash_arr[arr[j]] += 1
				f1 = True
			while i < j and match_cnt == k:
				ans += 1 + (n - 1 - j)
				i += 1
				hash_arr[arr[i]] -= 1
				if hash_arr[arr[i]] == 0:
					hash_arr.pop(arr[i])
					match_cnt -= 1
				f2 = True
			if f1 == False and f2 == False:
				break
		return ans


class Solution:

	def countDistinctSubarray(self, arr, n):
		k = len(set(arr))
		has = {}
		i = -1
		j = -1
		ans = 0
		while True:
			f1 = False
			f2 = False
			while i < n - 1:
				f1 = True
				i += 1
				has[arr[i]] = has.get(arr[i], 0) + 1
				if len(has) == k:
					ans += n - i
					break
			while j < i:
				f2 = True
				j += 1
				if has.get(arr[j]) == 1:
					has.pop(arr[j])
				else:
					has[arr[j]] -= 1
				if len(has) == k:
					ans += n - i
				else:
					break
			if f1 == False and f2 == False:
				break
		return ans


class Solution:

	def countDistinctSubarray(self, arr, n):
		total_ele = len(set(arr))
		count = {}
		right = 0
		window = 0
		ans = 0
		for i in range(n):
			while right < n and window < total_ele:
				if arr[right] in count:
					count[arr[right]] += 1
				else:
					count[arr[right]] = 1
				if count[arr[right]] == 1:
					window += 1
				right += 1
			if window == total_ele:
				ans += n - right + 1
			count[arr[i]] -= 1
			if count[arr[i]] == 0:
				window -= 1
		return ans


class Solution:

	def countDistinctSubarray(self, arr, n):
		(i, j) = (0, 0)
		m = {}
		count = 0
		ori = len(set(arr))
		ans = 0
		while j < n:
			if arr[j] not in m:
				m[arr[j]] = 1
				count += 1
			else:
				m[arr[j]] += 1
			while count == ori:
				ans += len(arr) - j
				m[arr[i]] -= 1
				if m[arr[i]] == 0:
					count -= 1
					m.pop(arr[i])
				i += 1
			j += 1
		return ans


class Solution:

	def countDistinctSubarray(self, arr, n):
		s = set(arr)
		cnt_distinct = len(s)
		ans = self.atmost(arr, cnt_distinct) - self.atmost(arr, cnt_distinct - 1)
		return ans

	def atmost(self, arr, B):
		i = 0
		j = 0
		d = {}
		cnt = 0
		while j < len(arr):
			if arr[j] in d:
				d[arr[j]] += 1
			else:
				d[arr[j]] = 1
			while len(d) > B:
				d[arr[i]] -= 1
				if d[arr[i]] == 0:
					d.pop(arr[i])
				i += 1
			cnt += j - i + 1
			j += 1
		return cnt


from collections import defaultdict

class Solution:

	def countDistinctSubarray(self, arr, n):
		total_distinct = len(set(arr))
		mp = defaultdict(lambda : 0)
		right = 0
		distinct = 0
		ans = 0
		for i in range(len(arr)):
			while right < n and distinct != total_distinct:
				if mp[arr[right]] == 0:
					distinct += 1
				mp[arr[right]] += 1
				right += 1
			if distinct == total_distinct:
				ans += n - right + 1
			if mp[arr[i]] == 1:
				distinct -= 1
			mp[arr[i]] -= 1
		return ans


def CountSubarrays(arr, n):
	freq = {i: 0 for i in arr}
	d = len(list(freq.keys()))
	(count, res, i) = (0, 0, 0)
	for j in range(n):
		freq[arr[j]] += 1
		if freq[arr[j]] == 1:
			count += 1
		if count == d:
			res += n - j
			while i <= j:
				freq[arr[i]] -= 1
				if freq[arr[i]] == 0:
					count -= 1
				i += 1
				if count == d:
					res += n - j
				else:
					break
	return res

class Solution:

	def countDistinctSubarray(self, arr, n):
		return CountSubarrays(arr, n)


class Solution:

	def countDistinctSubarray(self, arr, n):
		k = 0
		hashmap = {}
		for i in range(n):
			curr = arr[i]
			if curr in hashmap:
				hashmap[curr] += 1
			else:
				k += 1
				hashmap[curr] = 1

		def fun(k):
			left = dist = ans = 0
			hashmap = {}
			for right in range(len(arr)):
				curr = arr[right]
				if curr in hashmap:
					hashmap[curr] += 1
				else:
					hashmap[curr] = 1
					dist += 1
				while left <= right and dist > k:
					disc = arr[left]
					hashmap[disc] -= 1
					left += 1
					if hashmap[disc] == 0:
						del hashmap[disc]
						dist -= 1
				ans += right - left + 1
			return ans
		ans = fun(k) - fun(k - 1)
		return ans


from collections import defaultdict

class Solution:

	def countDistinctSubarray(self, arr, n):
		totalele = len(set(arr))
		ans = 0
		i = 0
		j = 0
		dp = defaultdict(int)
		while i < n:
			dp[arr[i]] += 1
			if len(dp) == totalele:
				ans += n - i
				while j <= i:
					if dp[arr[j]] == 1:
						dp.pop(arr[j])
						j += 1
						break
					else:
						dp[arr[j]] -= 1
					if len(dp) == totalele:
						ans += n - i
					j += 1
			i += 1
		return ans


class Solution:

	def countDistinctSubarray(self, arr, n):
		sp_set = set()
		for i in arr:
			sp_set.add(i)
		k = len(sp_set)
		dp = {}
		(right, window, ans) = (0, 0, 0)
		for left in range(n):
			while right < n and window < k:
				dp[arr[right]] = dp.get(arr[right], 0) + 1
				if dp[arr[right]] == 1:
					window += 1
				right += 1
			if window == k:
				ans += n - right + 1
			dp[arr[left]] -= 1
			if dp[arr[left]] == 0:
				window -= 1
		return ans
		return res


class Solution:

	def check_distinct(self, subarray_freq, unique_elem_hm):
		for key in unique_elem_hm:
			if subarray_freq[key] == 0:
				return False
		return True

	def countDistinctSubarray(self, nums, n):
		unique_elem_hm = {}
		for i in range(n):
			unique_elem_hm[nums[i]] = unique_elem_hm.get(nums[i], 0) + 1
		ans = 0
		unique_elem_count = 0
		subarray_freq = {}
		for key in unique_elem_hm:
			subarray_freq[key] = 0
			unique_elem_count += 1
		for i in range(unique_elem_count):
			subarray_freq[nums[i]] += 1
		l = 0
		r = unique_elem_count - 1
		while r < n and (not self.check_distinct(subarray_freq, unique_elem_hm)):
			r += 1
			subarray_freq[nums[r]] += 1
		ans += n - r
		while r < n:
			removed_elem = nums[l]
			l += 1
			subarray_freq[removed_elem] -= 1
			while r < n and subarray_freq[removed_elem] == 0:
				r += 1
				if r < n:
					subarray_freq[nums[r]] += 1
			ans += n - r
		return ans


class Solution:

	def mapAdd(self, dic, val):
		if val in dic:
			dic[val] += 1
		else:
			dic[val] = 1

	def mapSub(self, dic, val):
		dic[val] -= 1
		if dic[val] == 0:
			del dic[val]

	def getCount(self, arr):
		dSet = set()
		for val in arr:
			if val not in dSet:
				dSet.add(val)
		return len(dSet)

	def countDistinctSubarray(self, arr, n):
		count = self.getCount(arr)
		resCnt = 0
		currMap = {}
		lb = -1
		ub = -1
		while lb < len(arr) and ub < len(arr):
			if len(currMap) == count:
				resCnt += n - ub
				lb += 1
				self.mapSub(currMap, arr[lb])
			else:
				ub += 1
				if ub == n:
					return resCnt
				self.mapAdd(currMap, arr[ub])
		return resCnt


from collections import defaultdict

class Solution:

	def countDistinctSubarray(self, arr, n):
		expected = len(set(arr))
		total = 0
		ans = 0
		hmap = defaultdict(int)
		flag = False
		j = -1
		for i in range(n):
			hmap[arr[i]] += 1
			if hmap[arr[i]] == 1:
				total += 1
			while total == expected:
				flag = True
				j += 1
				hmap[arr[j]] -= 1
				if hmap[arr[j]] == 0:
					total -= 1
			if flag:
				ans += j + 1
		return ans


class Solution:

	def countDistinctSubarray(self, str, n):
		x = len(set(str))
		st = 0
		d = {}
		ans = 99999999
		l = 0
		c = 0
		r = False
		z = 0
		for i in range(n):
			if str[i] in d:
				d[str[i]] += 1
			else:
				d[str[i]] = 1
				l += 1
			if not r and l == x:
				c += (z + 1) * (n - i)
				r = True
			while st < i and d.get(str[st], 0) > 1:
				d[str[st]] -= 1
				st += 1
				if l == x:
					c += n - i
				else:
					z += 1
			if l == x:
				ans = min(ans, i - st + 1)
		return c


import collections

class Solution:

	def countDistinctSubarray(self, arr, n):
		l = 0
		r = 0
		count = 0
		alpha_ = {n: 1 for n in arr}
		map_ = collections.defaultdict(int)
		res = 0
		while r < len(arr):
			if arr[r] not in map_:
				map_[arr[r]] += 1
				count += 1
				if count == len(alpha_):
					a = 0
					temp = arr[l]
					while True:
						map_[arr[l]] -= 1
						a += 1
						if map_[arr[l]] == 0:
							del map_[arr[l]]
							count -= 1
							l += 1
							break
						l += 1
					b = len(arr) - r
					res += a * b
				r += 1
			else:
				map_[arr[r]] += 1
				r += 1
		return res


class Solution:

	def countDistinctSubarray(self, arr, n):
		(ans, cnt, start, k, di) = (0, 0, 0, len(set(arr)), dict())
		for i in range(n):
			while start < n and cnt < k:
				di[arr[start]] = di.get(arr[start], 0) + 1
				if di[arr[start]] == 1:
					cnt += 1
				start += 1
			if cnt == k:
				ans += n - start + 1
			di[arr[i]] -= 1
			cnt -= 1 if di[arr[i]] == 0 else 0
		return ans


class Solution:

	def countDistinctSubarray(self, arr, n):
		d = {}
		k = 0
		for i in arr:
			if i not in d:
				d[i] = 1
				k += 1
			else:
				d[i] += 1
		l = 0
		r = 0
		x = 0
		dl = {}
		s = 0
		for i in range(n):
			if arr[i] not in dl:
				dl[arr[i]] = 1
				s += 1
			else:
				dl[arr[i]] += 1
			if s == k:
				x += n - i
				while s == k:
					dl[arr[l]] -= 1
					if dl[arr[l]] == 0:
						del dl[arr[l]]
						s -= 1
					else:
						x += n - i
					l += 1
		return x
t = int(input())
for _ in range(0, t):
	n = int(input())
	a = list(map(int, input().split()))
	ob = Solution()
	print(ob.countDistinctSubarray(a, n))


class Solution:

	def countDistinctSubarray(self, arr, n):
		e = 0
		d = {}
		for i in range(n):
			if arr[i] not in d:
				d[arr[i]] = 1
				e += 1
		d = {}
		i = 0
		j = n - 1
		while i < n:
			if arr[i] in d:
				d[arr[i]] += 1
			else:
				d[arr[i]] = 1
			if len(d) == e:
				r = i
				break
			i += 1
		i = 0
		c = 0
		while r < n:
			if len(d) == e:
				c += n - r
				d[arr[i]] -= 1
				if d[arr[i]] == 0:
					del d[arr[i]]
				i += 1
			else:
				r += 1
				if r < n and arr[r] not in d:
					d[arr[r]] = 1
				elif r < n:
					d[arr[r]] += 1
		return c
t = int(input())
for _ in range(0, t):
	n = int(input())
	a = list(map(int, input().split()))
	ob = Solution()
	print(ob.countDistinctSubarray(a, n))


class Solution:

	def countDistinctSubarray(self, arr, n):
		count = {}
		for i in range(len(arr)):
			count[arr[i]] = 1 + count.get(arr[i], 0)
		distinct = len(count)
		res = {}
		l = 0
		ans = 0
		for r in range(n):
			res[arr[r]] = 1 + res.get(arr[r], 0)
			while len(res) == distinct:
				ans += n - r
				res[arr[l]] -= 1
				if res[arr[l]] == 0:
					del res[arr[l]]
				l += 1
		return ans
t = int(input())
for _ in range(0, t):
	n = int(input())
	a = list(map(int, input().split()))
	ob = Solution()
	print(ob.countDistinctSubarray(a, n))


class Solution:

	def countDistinctSubarray(self, arr, n):
		d = {}
		for i in range(n):
			d[arr[i]] = 1
		p = len(d)
		d1 = {}
		h = 0
		res = 0
		l = 0
		for i in range(n):
			d1[arr[i]] = d1.get(arr[i], 0) + 1
			if arr[i] in d and d[arr[i]] == d1[arr[i]]:
				h += 1
			while p == h:
				d1[arr[l]] -= 1
				if arr[l] in d and d[arr[i]] > d1[arr[l]]:
					h -= 1
				res += n - i
				l += 1
		return res
t = int(input())
for _ in range(0, t):
	n = int(input())
	a = list(map(int, input().split()))
	ob = Solution()
	print(ob.countDistinctSubarray(a, n))


class Solution:

	def countDistinctSubarray(self, arr, n):
		vis = dict()
		for i in range(n):
			vis[arr[i]] = 1
		k = len(vis)
		vid = dict()
		ans = 0
		right = 0
		window = 0
		for left in range(n):
			while right < n and window < k:
				if arr[right] in vid.keys():
					vid[arr[right]] += 1
				else:
					vid[arr[right]] = 1
				if vid[arr[right]] == 1:
					window += 1
				right += 1
			if window == k:
				ans += n - right + 1
			vid[arr[left]] -= 1
			if vid[arr[left]] == 0:
				window -= 1
		return ans
t = int(input())
for _ in range(0, t):
	n = int(input())
	a = list(map(int, input().split()))
	ob = Solution()
	print(ob.countDistinctSubarray(a, n))


class Solution:

	def countDistinctSubarray(self, l, n):
		d = {}
		for x in l:
			d[x] = 0
		k = len(d)
		i = 0
		j = 0
		ans = 0
		count = 0
		while i < len(l):
			if d[l[i]] == 0:
				ans += 1
			d[l[i]] += 1
			while ans == k and j <= i:
				count += len(l) - i
				d[l[j]] -= 1
				if d[l[j]] == 0:
					ans -= 1
				j += 1
			i += 1
		return count
t = int(input())
for _ in range(0, t):
	n = int(input())
	a = list(map(int, input().split()))
	ob = Solution()
	print(ob.countDistinctSubarray(a, n))


class Solution:

	def countDistinctSubarray(self, arr, n):
		(uniq, d) = (len(set(arr)), {})
		start = c = tot = 0
		for i in range(n):
			if arr[i] not in d:
				(d[arr[i]], c) = (1, c + 1)
			else:
				d[arr[i]] += 1
			if c == uniq:
				tot += n - i
				break
		while start < n:
			c -= d[arr[start]] == 1
			d[arr[start]] -= 1
			start += 1
			while c < uniq:
				i += 1
				if i >= n:
					break
				if arr[i] not in d or d[arr[i]] == 0:
					(d[arr[i]], c) = (1, c + 1)
				else:
					d[arr[i]] += 1
			tot += n - i if c == uniq else 0
		return tot
t = int(input())
for _ in range(0, t):
	n = int(input())
	a = list(map(int, input().split()))
	ob = Solution()
	print(ob.countDistinctSubarray(a, n))


class Solution:

	def countDistinctSubarray(self, arr, n):
		k = len(set(arr))
		unique = {}
		i = ans = 0
		for j in range(len(arr)):
			if arr[j] not in unique:
				unique[arr[j]] = 1
			else:
				unique[arr[j]] += 1
			while len(unique) == k:
				ans += len(arr) - j
				unique[arr[i]] -= 1
				if unique[arr[i]] == 0:
					del unique[arr[i]]
				i += 1
		return ans


class Solution:

	def atMostK(self, arr, n, k):
		count = 0
		left = 0
		right = 0
		map = {}
		while right < n:
			if arr[right] not in map:
				map[arr[right]] = 0
			map[arr[right]] += 1
			while len(map) > k:
				if arr[left] not in map:
					map[arr[left]] = 0
				map[arr[left]] -= 1
				if map[arr[left]] == 0:
					del map[arr[left]]
				left += 1
			count += right - left + 1
			right += 1
		return count

	def countDistinctSubarray(self, arr, n):
		d = dict()
		k = 0
		for i in arr:
			if d.get(i) == None:
				k = k + 1
				d[i] = True
		return self.atMostK(arr, n, k) - self.atMostK(arr, n, k - 1)


class Solution:

	def countDistinctSubarray(self, arr, n):
		a = [0] * 100000
		k = 0
		for i in range(n):
			if a[arr[i]] == 0:
				a[arr[i]] += 1
				k += 1
			else:
				a[arr[i]] += 1
		a = [0] * 1000000
		value = 0
		z = 0
		res = 0
		value = 0
		for i in range(n):
			if a[arr[i]] == 0:
				a[arr[i]] += 1
				z += 1
			else:
				a[arr[i]] += 1
			if z == k:
				while value <= i:
					if a[arr[value]] >= 1:
						res += n - i
						a[arr[value]] -= 1
						if a[arr[value]] == 0:
							z -= 1
							break
						value += 1
					else:
						break
				value += 1
			if i == n - 1:
				break
		return res


from collections import defaultdict

class Solution:

	def countDistinctSubarray(self, num, n):
		i = 0
		j = 0
		l = len(set(num))
		n = len(num)
		d = defaultdict(int)
		c = 0
		cnt = 0
		while i < n and j < n:
			if d[num[j]] == 0:
				c += 1
			d[num[j]] += 1
			while i <= j and c == l:
				cnt += n - j
				d[num[i]] -= 1
				if d[num[i]] == 0:
					c -= 1
				i += 1
			j += 1
		return cnt


class Solution:

	def countDistinctSubarray(self, a, n):
		w = len(set(a))
		count = 0
		i = 0
		d = {}
		s = 0
		for i in range(n):
			d[a[i]] = d.get(a[i], 0) + 1
			while len(d) >= w:
				count += n - i
				d[a[s]] -= 1
				if d[a[s]] == 0:
					d.pop(a[s])
				s += 1
		return count


class Solution:

	def countDistinctSubarray(self, arr, n):
		set1 = set(arr)
		distinct_count = len(set1)
		(start, end) = (0, 0)
		count = 0
		res = 0
		d = {}
		for i in range(0, n):
			if arr[i] in set1:
				d[arr[i]] = 1 + d.get(arr[i], 0)
				if len(d) == distinct_count:
					while len(d) == distinct_count:
						res += n - i
						d[arr[start]] -= 1
						if d[arr[start]] == 0:
							d.pop(arr[start])
						start += 1
		return res


class Solution:

	def countDistinctSubarray(self, arr, n):
		l = len(set(arr))
		dp = {}
		for xi in arr:
			dp[xi] = 0
		solve = 0
		c = 0
		i = 0
		j = 0
		while j < n:
			dp[arr[j]] += 1
			if dp[arr[j]] == 1:
				c += 1
			while c == l:
				solve += n - j
				dp[arr[i]] -= 1
				if dp[arr[i]] == 0:
					c -= 1
				i += 1
			j += 1
		return solve


class Solution:

	def countDistinctSubarray(self, arr, n):
		tot = 0
		mp = {}
		for i in arr:
			if i not in mp:
				mp[i] = 0
				tot += 1
		mp = {}
		l = 0
		r = 0
		tem = 0
		while True:
			if tem == tot:
				break
			if arr[r] not in mp:
				mp[arr[r]] = 0
				tem += 1
			mp[arr[r]] += 1
			if tem == tot:
				break
			r += 1
		ans = 0
		ans += n - r
		tog = 0
		while l < n and r < n:
			if tog == 0:
				mp[arr[l]] -= 1
				if mp[arr[l]] != 0:
					ans += n - r
					l += 1
					continue
				else:
					tog = 1
					find = arr[l]
					l += 1
			else:
				r += 1
				while r < n and arr[r] != find:
					mp[arr[r]] += 1
					r += 1
				if r == n:
					break
				mp[arr[r]] += 1
				tog = 0
				ans += n - r
		return ans


class Solution:

	def countDistinctSubarray(self, arr, n):
		s = set(arr)
		d = {e: 0 for e in s}
		(z, k) = (0, 0)
		ns = set()
		c = 0
		while k < len(arr):
			ns.add(arr[k])
			d[arr[k]] += 1
			k += 1
			while len(ns) == len(s):
				c += len(arr) - k + 1
				d[arr[z]] -= 1
				if not d[arr[z]]:
					ns.remove(arr[z])
				z += 1
		return c


from collections import defaultdict

class Solution:

	def countDistinctSubarray(self, arr, n):
		s = set(arr)
		distinct = len(s)
		d = defaultdict(int)
		j = 0
		count = 0
		for i in range(n):
			d[arr[i]] += 1
			while len(d) >= distinct and j <= i:
				count += n - i
				d[arr[j]] -= 1
				if d[arr[j]] == 0:
					del d[arr[j]]
				j += 1
		return count


class Solution:

	def countDistinctSubarray(self, arr, n):
		k = set(arr)
		req = len(k)
		mp = {}
		ans = 0
		i = 0
		j = 0
		while j < n:
			if arr[j] not in mp:
				mp[arr[j]] = 1
			else:
				mp[arr[j]] += 1
			while i <= j and len(mp) == req:
				ans += n - j
				mp[arr[i]] -= 1
				if mp[arr[i]] == 0:
					del mp[arr[i]]
				i += 1
			j += 1
		return ans


class Solution:

	def countDistinctSubarray(self, arr, n):
		d = {}
		for i in arr:
			d[i] = d.get(i, 0) + 1
		r = 0
		k = len(d)
		d = {}
		ans = 0
		countdist = 0
		for l in range(0, n):
			while r < n and countdist < k:
				d[arr[r]] = d.get(arr[r], 0) + 1
				if d[arr[r]] == 1:
					countdist += 1
				r += 1
			if countdist == k:
				ans += n - r + 1
				d[arr[l]] -= 1
				if d.get(arr[l], 0) == 0:
					countdist -= 1
		return ans


from collections import defaultdict

class Solution:

	def countDistinctSubarray(self, arr, n):
		mp = defaultdict()
		for i in range(n):
			mp[arr[i]] = mp.get(arr[i], 0) + 1
		k = len(mp)
		mp.clear()
		(ans, p) = (0, 0)
		for i in range(n):
			mp[arr[i]] = mp.get(arr[i], 0) + 1
			while len(mp) == k:
				ans += n - i
				mp[arr[p]] -= 1
				if mp[a[p]] == 0:
					del mp[arr[p]]
				p += 1
		return ans


class Solution:

	def countDistinctSubarray(self, arr, n):
		counter = dict.fromkeys(arr, 0)
		zeroset = set(arr)
		count = 0
		(i, j, count) = (0, -1, 0)
		while i < n and j < n:
			while len(zeroset) > 0:
				j = j + 1
				if j >= n:
					break
				counter[arr[j]] += 1
				if arr[j] in zeroset:
					zeroset.remove(arr[j])
			else:
				inc = n - j
				count += inc
			counter[arr[i]] = max(0, counter[arr[i]] - 1)
			if counter[arr[i]] == 0:
				zeroset.add(arr[i])
			i = i + 1
			if i >= n:
				break
		return count


from collections import defaultdict

class Solution:

	def countDistinctSubarray(self, arr, n):
		hassh = set()
		for i in arr:
			hassh.add(i)
		dist = len(hassh)
		left = 0
		h = {}
		ans = 0
		for right in range(0, n):
			h[arr[right]] = 1 + h.get(arr[right], 0)
			while len(h) == dist:
				ans += n - right
				h[arr[left]] -= 1
				if h[arr[left]] == 0:
					h.pop(arr[left])
				left += 1
		return ans


class Solution:

	def distinct(self, arr, start, end):
		d = dict()
		c = 0
		for i in range(start, end):
			if arr[i] not in d:
				c += 1
				d[arr[i]] = 1
		return c

	def countDistinctSubarray(self, arr, n):
		res = 0
		c = self.distinct(arr, 0, n)
		d = dict()
		start = 0
		i = 0
		while start < n:
			if arr[i] not in d:
				d[arr[i]] = 1
			else:
				d[arr[i]] += 1
			if len(d) == c:
				res += n - i
			while len(d) == c:
				if d[arr[start]] == 1:
					del d[arr[start]]
				else:
					d[arr[start]] -= 1
				if len(d) == c:
					res += n - i
				start += 1
			if len(d) < c and i == n - 1:
				break
			if i < n - 1:
				i += 1
		return res


from collections import defaultdict

class Solution:

	def countDistinctSubarray(self, arr, n):
		dist_num = len(set(arr))
		(left, right) = (0, 0)
		res = 0
		mapa = defaultdict(int)
		while left < n:
			mapa[arr[left]] += 1
			if len(mapa) == dist_num:
				res += n - left
				while right <= left:
					if mapa[arr[right]] == 1:
						mapa.pop(arr[right])
						right += 1
						break
					else:
						mapa[arr[right]] -= 1
					if len(mapa) == dist_num:
						res += n - left
					right += 1
			left += 1
		return res


from collections import Counter

class Solution:

	def countDistinctSubarray(self, arr, n):
		arr_c = Counter(arr)
		k = len(arr_c)
		l = 0
		r = 0
		window = 1
		m = dict()
		count = 0
		m[arr[l]] = 1
		while r < n:
			if window == k:
				count += n - r
				m[arr[l]] = m[arr[l]] - 1
				if m[arr[l]] == 0:
					del m[arr[l]]
					window -= 1
				l += 1
			else:
				r += 1
				if r >= n:
					break
				if m.get(arr[r]):
					m[arr[r]] += 1
				else:
					m[arr[r]] = 1
					window += 1
		return count


from collections import defaultdict as dc

class Solution:

	def countDistinctSubarray(self, a, n):
		vis = dc(int)
		vid = dc(int)
		for i in a:
			vis[i] = 1
		l = len(vis.keys())
		ans = 0
		right = 0
		window = 0
		for left in range(n):
			while right < n and window < l:
				vid[a[right]] += 1
				if vid[a[right]] == 1:
					window += 1
				right += 1
			if window == l:
				ans += n - right + 1
			vid[a[left]] -= 1
			if vid[a[left]] == 0:
				window -= 1
		return ans


from collections import Counter

class Solution:

	def countDistinctSubarray(self, arr, n):
		delem = len(Counter(arr))
		(left, count) = (0, 0)
		w = Counter()
		for (i, e) in enumerate(arr):
			w[e] += 1
			while len(w) == delem and left < n:
				count += n - i
				w[arr[left]] -= 1
				if w[arr[left]] == 0:
					del w[arr[left]]
				left += 1
		return count


class Solution:

	def countDistinctSubarray(self, arr, n):
		d = {}
		for i in arr:
			d[i] = 0
		k = len(d)
		(count, j, w) = (0, 0, 0)
		for i in range(n):
			while k != w and j < n:
				d[arr[j]] += 1
				if d[arr[j]] == 1:
					w += 1
				j += 1
			if w == k:
				count += n - j + 1
			d[arr[i]] -= 1
			if d[arr[i]] == 0:
				w -= 1
		return count