Given an array containing N elements. The task is to find the maximum number of distinct elements after removing K elements from the array. 
Example 1:
Input : Arr[] = {5, 7, 5, 5, 1, 2, 2}, K = 3
Output : 4
Explanation:
Remove 2 occurrences of element 5 and 
1 occurrence of element 2.
Example 2:
Input : Arr[] = {1, 2, 3, 4, 5, 6, 7}, K = 5
Output : 2
Your Task:
This is a function problem. The input is already taken care of by the driver code. You only need to complete the function maxDistinctNum() that takes an array (arr), sizeOfArray (n), integer value K, and return the maximum distinct elements after removing K elements. The driver code takes care of the printing.
Expected Time Complexity: O(K*logD)  where D is the number of distinct elements in the given array.
Expected Auxiliary Space: O(N).
 
Constraints:
1 ≤ K ≤ N ≤ 10^{6}
1 ≤ A[i] ≤ 10^{5}

Source: geeksforgeeks | Difficulty: EASY
Tags: String algorithms

Data structures

Starter code: #User function Template for python3

class Solution:
    def maxTripletSum (self, arr,  n, K) : 
        #Complete the function


Solutions:
import heapq as h

class Solution:

	def maxTripletSum(self, arr, n, K):
		hashmap = {}
		maxheap = []
		for i in range(0, n):
			if arr[i] in hashmap:
				hashmap[arr[i]] = hashmap[arr[i]] + 1
			elif arr[i] not in hashmap:
				hashmap[arr[i]] = 1
		for (key, value) in hashmap.items():
			h.heappush(maxheap, -value)
		while K > 0:
			if maxheap:
				temp = -h.heappop(maxheap)
				temp = temp - 1
				K = K - 1
				if temp > 0:
					h.heappush(maxheap, -temp)
		return len(maxheap)


import heapq
from collections import defaultdict

class Solution:

	def maxTripletSum(self, arr, n, K):
		hmap = defaultdict(int)
		for i in range(0, n):
			if arr[i] not in hmap:
				hmap[arr[i]] = 1
			else:
				hmap[arr[i]] += 1
		maxheap = []
		for (key, value) in hmap.items():
			heapq.heappush(maxheap, -value)
		for i in range(0, K):
			ele = -heapq.heappop(maxheap)
			if ele - 1 != 0:
				heapq.heappush(maxheap, -(ele - 1))
		return len(maxheap)


class Solution:

	def maxTripletSum(self, arr, n, k):
		s = set(arr)
		a = len(arr) - len(s)
		if a >= k:
			return len(s)
		else:
			return len(arr) - k


import heapq

class Solution:

	def maxTripletSum(self, a, n, k):
		s = {}
		for i in range(n):
			if a[i] not in s or k == 0:
				s[a[i]] = s.get(a[i], 0) + 1
			else:
				s[a[i]] = 1
				k -= 1
		if k != 0:
			if len(s) - k < 0:
				return -1
			return len(s) - k
		return len(s)


class Solution:

	def maxTripletSum(self, arr, n, k):
		lena = len(arr)
		lens = len(set(arr))
		excess = lena - lens
		return lens if excess >= k else max(0, lena - k)


class Solution:

	def maxTripletSum(self, arr, n, k):
		d = {}
		c = 0
		for i in arr:
			if i in d:
				c += 1
			else:
				d[i] = 1
		if c >= k:
			return len(d)
		return len(d) - (k - c)


class Solution:

	def maxTripletSum(self, arr, n, K):
		arr_set = set(arr)
		if len(arr) - len(arr_set) > K:
			return len(arr_set)
		return len(arr) - K


class Solution:

	def maxTripletSum(self, arr, n, K):
		arr.sort()
		temp = arr[0]
		while K > 0 and n > 0:
			if arr[n - 1] == temp:
				arr.pop(n - 1)
				K -= 1
			else:
				temp = arr[n - 1]
			n -= 1
		while K > 0:
			arr.pop()
			K -= 1
		return len(set(arr))


class Solution:

	def maxTripletSum(self, arr, n, k):
		a = set(arr)
		l = len(a)
		b = n - l
		if b >= k:
			return l
		else:
			return l - (k - b)


import heapq

class Solution:

	def maxTripletSum(self, arr, n, K):
		d = {}
		for i in arr:
			if i in d:
				d[i] += 1
			else:
				d[i] = 1
		freq = []
		for j in d:
			heapq.heappush(freq, -1 * d[j])
		for i in range(K):
			top = -1 * freq[0]
			heapq.heappop(freq)
			if top >= 1:
				if top - 1 == 0:
					continue
				else:
					heapq.heappush(freq, -1 * (top - 1))
		return len(freq)


class Solution:

	def maxTripletSum(self, arr, n, K):
		arr = set(arr)
		K = K - (n - len(arr))
		if K <= 0:
			return len(arr)
		else:
			return len(arr) - K


import bisect

class Solution:

	def maxTripletSum(self, arr, n, K):
		d = {}
		for i in arr:
			if i not in d:
				d[i] = 1
			else:
				d[i] += 1
		d1 = sorted(d.values())
		d1.sort()
		c = 0
		while c != K and d1 != []:
			a = d1[-1]
			d1.pop()
			a = a - 1
			bisect.insort(d1, a)
			c += 1
		c1 = 0
		for i in d1:
			if i > 0:
				c1 += 1
		return c1


from heapq import *

class Solution:

	def maxTripletSum(self, arr, n, k):
		counter = {}
		for num in arr:
			counter[num] = counter.get(num, 0) + 1
		heap = [(-freq, num) for (num, freq) in counter.items()]
		heapify(heap)
		for _ in range(k):
			if not heap:
				return 0
			(nfreq, num) = heappop(heap)
			new_freq = nfreq + 1
			if new_freq < 0:
				heappush(heap, (new_freq, num))
		return len(heap)


class Solution:

	def heapify(self, arr, n, i):
		largest = i
		l = 2 * i + 1
		r = 2 * i + 2
		if l < n and self.mp[arr[l]] > self.mp[arr[largest]]:
			largest = l
		if r < n and self.mp[arr[r]] > self.mp[arr[largest]]:
			largest = r
		if largest != i:
			(arr[i], arr[largest]) = (arr[largest], arr[i])
			self.heapify(arr, n, largest)

	def maxTripletSum(self, arr, n, k):
		self.mp = {}
		heap = []
		for x in arr:
			if x in self.mp:
				self.mp[x] += 1
			else:
				self.mp[x] = 1
				heap.append(x)
		m = len(heap)
		for i in range(int(m / 2) - 1, -1, -1):
			self.heapify(heap, m, i)
		for i in range(k):
			self.mp[heap[0]] -= 1
			self.heapify(heap, m, 0)
		res = 0
		for x in heap:
			if self.mp[x] > 0:
				res += 1
		return res


class Solution:

	def heapify(self, arr, n, i):
		l = 2 * i + 1
		r = 2 * i + 2
		largest = i
		if l < n and self.mp[arr[l]] > self.mp[arr[largest]]:
			largest = l
		if r < n and self.mp[arr[r]] > self.mp[arr[largest]]:
			largest = r
		if largest != i:
			(arr[i], arr[largest]) = (arr[largest], arr[i])
			self.heapify(arr, n, largest)

	def maxTripletSum(self, arr, n, k):
		self.mp = {}
		dis_arr = []
		for x in arr:
			if x in self.mp:
				self.mp[x] += 1
			else:
				dis_arr.append(x)
				self.mp[x] = 1
		for i in range(len(dis_arr) // 2 - 1, -1, -1):
			self.heapify(dis_arr, len(dis_arr), i)
		for i in range(k):
			ele = dis_arr[0]
			if self.mp[ele] > 1:
				self.mp[ele] -= 1
				self.heapify(dis_arr, len(dis_arr), 0)
			else:
				dis_arr.pop(0)
		return len(dis_arr)


import heapq

class Solution:

	def maxTripletSum(self, arr, n, K):
		return min(len(set(arr)), n - K)


import heapq

class Solution:

	def maxTripletSum(self, arr, n, K):
		mp = {}
		for i in arr:
			if i not in mp:
				mp[i] = 1
			else:
				mp[i] += 1
		freq = []
		for key in mp:
			heapq.heappush(freq, -1 * mp[key])
		for i in range(K):
			top = -1 * freq[0]
			heapq.heappop(freq)
			if top >= 1:
				if top - 1 == 0:
					continue
				else:
					heapq.heappush(freq, -1 * (top - 1))
		return len(freq)


from collections import Counter

class Solution:

	def maxTripletSum(self, arr, n, K):
		c = Counter(arr)
		count = 0
		for item in c:
			count += 1
			K -= c[item] - 1
		return count - max(0, K)


class Solution:

	def maxTripletSum(self, arr, n, K):
		kt = {}
		for x in arr:
			if x not in kt.keys() or kt[x] == 0:
				kt[x] = 1
			else:
				K -= 1
		return len(kt) - max(K, 0)


class Solution:

	def maxTripletSum(self, a, n, k):
		s = {}
		for i in range(n):
			if a[i] not in s or k == 0:
				s[a[i]] = s.get(a[i], 0) + 1
			else:
				s[a[i]] = 1
				k -= 1
		if k != 0:
			return len(s) - k
		else:
			st = set()
			for i in s:
				st.add(i)
			return len(st)


class Solution:

	def maxTripletSum(self, arr, n, K):
		freq = dict()
		for num in arr:
			if num in freq:
				freq[num] += 1
				if K > 0:
					K = K - 1
			else:
				freq[num] = 1
		return len(freq) - K


from queue import PriorityQueue

class Solution:

	def maxTripletSum(self, arr, n, K):
		q = PriorityQueue()
		h = {}
		for i in arr:
			if i not in h.keys():
				h[i] = 1
			else:
				h[i] += 1
		l = len(h)
		v = list(h.keys())
		for i in v:
			q.put([-h[i], i])
		while K > 0:
			t = q.get()
			t[0] += 1
			if t[0] != 0:
				q.put([t[0], t[1]])
			K -= 1
		return q.qsize()


class Solution:

	def maxTripletSum(self, arr, n, K):
		nums_set = set()
		for num in arr:
			if num in nums_set:
				K -= 1
			else:
				nums_set.add(num)
		return len(nums_set) - K if K > 0 else len(nums_set)


import heapq

class Solution:

	def maxTripletSum(self, arr, n, K):
		dic = {}
		cnt = 0
		for i in arr:
			dic[i] = dic.get(i, 0) + 1
		l = [-i for i in list(dic.values())]
		heapq.heapify(l)
		while K > 0:
			temp = heapq.heappop(l)
			temp += 1
			heapq.heappush(l, temp)
			K -= 1
		for i in l:
			if i == 0:
				cnt += 1
		return len(l) - cnt


class Solution:

	def maxTripletSum(self, arr, n, K):
		dic = {}
		i = 0
		while i < len(arr):
			if arr[i] not in dic:
				dic[arr[i]] = 1
			else:
				arr.pop(i)
				i -= 1
				K -= 1
			i += 1
		if K > 0:
			return len(arr) - K
		else:
			return len(arr)


class Solution:

	def maxTripletSum(self, arr, n, k):
		dic = {}
		for i in arr:
			if i in dic and k > 0:
				k -= 1
			else:
				dic[i] = 1
		if k > 0:
			return len(dic) - k
		else:
			return len(dic)


import heapq

class Solution:

	def maxTripletSum(self, arr, n, K):
		numFrequencyMap = {}
		maxHeap = []
		for num in arr:
			numFrequencyMap[num] = numFrequencyMap.get(num, 0) + 1
		for (num, frequency) in numFrequencyMap.items():
			heapq.heappush(maxHeap, (-frequency, num))
		for _ in range(K):
			pair = heapq.heappop(maxHeap)
			if pair[0] < -1:
				heapq.heappush(maxHeap, (pair[0] + 1, pair[1]))
		return len(maxHeap)


class Solution:

	def maxTripletSum(self, arr, n, K):
		(c1, c2) = (0, 0)
		res = set()
		for i in arr:
			if i not in res:
				c1 += 1
				res.add(i)
			else:
				c2 += 1
		if c2 > K:
			return c1
		else:
			return c1 + c2 - K


import heapq
import math

class Solution:

	def maxTripletSum(self, arr, n, k):
		d = {}
		count = 0
		for i in arr:
			d[i] = d.get(i, 0) + 1
		l = [int(ele) for ele in d.values()]
		heapq._heapify_max(l)
		for i in range(k):
			l[0] -= 1
			heapq._heapreplace_max(l, l[0])
		for i in l:
			if i == 0:
				continue
			else:
				count += 1
		return count


import heapq
import math

class Solution:

	def maxTripletSum(self, arr, n, K):
		arr = set(arr)
		K -= n - len(arr)
		return len(arr) if K <= 0 else len(arr) - K


from collections import Counter

class Solution:

	def maxTripletSum(self, arr, n, K):
		m = Counter(arr)
		cnt = []
		values = list(m.values())
		while sum(values) > len(values):
			for i in range(len(values)):
				if values[i] > 1:
					values[i] -= 1
					K = K - 1
		if K > 0:
			return len(values) - K
		else:
			return len(values)


import heapq

class MaxHeap:

	def __init__(self, data=None):
		if data is None:
			self.data = []
		else:
			self.data = [-i for i in data]
			heapq.heapify(self.data)

	def push(self, item):
		heapq.heappush(self.data, -item)

	def pop(self):
		return -heapq.heappop(self.data)

	def replace(self, item):
		return heapq.heapreplace(self.data, -item)

	def top(self):
		return -self.data[0]

class Solution:

	def maxTripletSum(self, arr, n, K):
		info = {}
		for num in arr:
			if num in info:
				info[num] += 1
			else:
				info[num] = 1
		max_heap = []
		for (num, freq) in info.items():
			heapq.heappush(max_heap, (-freq, num))
		count_removed = 0
		max_distinct = len(info)
		while count_removed < K:
			if not max_heap:
				return max_distinct - (K - count_removed)
			(freq, num) = heapq.heappop(max_heap)
			freq = -1 * freq
			if freq > 1:
				count_removed += freq - 1
			elif freq == 1:
				count_removed += 1
				max_distinct -= 1
		return max_distinct


import collections, heapq

class Solution:

	def maxTripletSum(self, arr, n, K):
		freq = collections.Counter(arr)
		maxHeap = []
		for (number, count) in freq.items():
			heapq.heappush(maxHeap, [-count, number])
		while K > 0:
			(c, number) = heapq.heappop(maxHeap)
			count = -c
			count -= 1
			if count > 0:
				heapq.heappush(maxHeap, [-count, number])
			K -= 1
		return len(maxHeap)


import heapq

class Solution:

	def maxTripletSum(self, arr, n, K):
		heap = []
		count = {}
		for num in arr:
			count[num] = count.get(num, 0) + 1
		for key in count.keys():
			heapq.heappush(heap, (-1 * count[key], key))
		removed = 0
		while removed != K:
			(c, val) = heapq.heappop(heap)
			c = c * -1 - 1
			if c > 0:
				heapq.heappush(heap, (-1 * c, val))
			removed += 1
		return len(heap)


class Solution:

	def maxTripletSum(self, arr, n, K):
		res = {}
		for i in range(n):
			if arr[i] not in res:
				res[arr[i]] = 1
		t = n - K
		if t <= len(res):
			return t
		return len(res)


class Solution:

	def maxTripletSum(self, arr, n, K):
		l = set(arr)
		p = len(l)
		if p + K <= n:
			return p
		else:
			return n - K


from collections import Counter
import heapq

class Solution:

	def maxTripletSum(self, arr, n, K):
		numFreq = Counter(arr)
		heap = []
		for (key, val) in numFreq.items():
			heapq.heappush(heap, (-val, key))
		if K > n:
			return 0
		for i in range(K):
			(val, key) = heapq.heappop(heap)
			val = -val - 1
			if val > 0:
				heapq.heappush(heap, (-val, key))
		cnt = 0
		while heap:
			heapq.heappop(heap)
			cnt += 1
		return cnt


class Solution:

	def maxTripletSum(self, arr, n, K):
		extra = 0
		table = {}
		for i in range(n):
			if arr[i] in table:
				table[arr[i]] += 1
				extra += 1
			else:
				table[arr[i]] = 1
		distinct = len(table)
		if K <= extra:
			return distinct
		else:
			distinct = distinct - (K - extra)
			return distinct


class Solution:

	def maxTripletSum(self, arr, n, K):
		sdict = {}
		count = 0
		for ele in arr:
			sdict[ele] = sdict.get(ele, 0) + 1
			if sdict[ele] > 1:
				sdict[ele] -= 1
				count += 1
				K -= 1
		res = 0
		if K == 0:
			res = len(arr) - count
		elif K > 0:
			res = len(sdict) - K
		else:
			res = len(sdict)
		return res


from collections import Counter

class Solution:

	def maxTripletSum(self, arr, n, K):
		d = Counter(arr)
		lst = []
		for i in d:
			lst.append(d[i])
		if K >= n:
			return 0
		lst = sorted(lst, reverse=True)
		for i in range(len(lst)):
			if lst[i] > 1:
				K -= lst[i] - 1
				lst[i] = 1
			if K <= 0:
				return len(lst)
		return len(lst) - K


class Solution:

	def maxTripletSum(self, arr, n, K):
		aset = set(arr)
		m = len(aset)
		if K > n - m:
			return m - (K - (n - m))
		return m
for _ in range(0, int(input())):
	(n, K) = map(int, input().split())
	arr = list(map(int, input().strip().split()))
	ob = Solution()
	res = ob.maxTripletSum(arr, n, K)
	print(res)


class Solution:

	def maxTripletSum(self, arr, n, K):
		s = set(arr)
		l = len(s)
		if K < n - l:
			return l
		else:
			return n - K
for _ in range(0, int(input())):
	(n, K) = map(int, input().split())
	arr = list(map(int, input().strip().split()))
	ob = Solution()
	res = ob.maxTripletSum(arr, n, K)
	print(res)


import heapq as h

class Solution:

	def maxTripletSum(self, arr, n, K):
		elems = {}
		for i in arr:
			if i in elems.keys():
				if K != 0:
					K -= 1
			else:
				elems[i] = 1
		if K != 0:
			return len(elems) - K
		else:
			return len(elems)
for _ in range(0, int(input())):
	(n, K) = map(int, input().split())
	arr = list(map(int, input().strip().split()))
	ob = Solution()
	res = ob.maxTripletSum(arr, n, K)
	print(res)


import collections
import heapq

class Solution:

	def maxTripletSum(self, arr, n, K):
		if K > n:
			return 0
		FreqAndNum = collections.namedtuple('FreqAndNum', ['frequency', 'num'])
		freq_map = {}
		for i in arr:
			freq_map[i] = freq_map.get(i, 0) + 1
		if n - K >= len(freq_map):
			return len(freq_map)
		else:
			return len(freq_map) - (K - (n - len(freq_map)))


from collections import Counter as C

class Solution:

	def maxTripletSum(self, a, n, k):
		if n - len(set(a)) >= k:
			return len(set(a))
		else:
			k -= n - len(set(a))
			return len(set(a)) - k


from heapq import heapify, heappop, heappush

class Solution:

	def maxTripletSum(self, arr, n, K):
		frequency = dict()
		for num in arr:
			if num in frequency:
				frequency[num] += 1
			else:
				frequency[num] = 1
		pair = []
		for key in frequency.keys():
			pair.append((frequency[key] * -1, key * -1))
		heapify(pair)
		while K > 0 and pair:
			(count, key) = heappop(pair)
			count *= -1
			if count - 1 > 0:
				heappush(pair, ((count - 1) * -1, key))
			K -= 1
		return len(pair)


class Solution:

	def maxTripletSum(self, arr, n, K):
		d = len(set(arr))
		if K == n - d:
			return n - K
		elif K > n - d:
			K = K - (n - d)
			return d - K
		else:
			return d


class Solution:

	def maxTripletSum(self, arr, N, k):
		mp = {}
		for i in range(N):
			if arr[i] not in mp:
				mp[arr[i]] = 0
			mp[arr[i]] += 1
		v1 = []
		for i in mp:
			v1.append(mp[i])
		temp = 0
		for i in range(len(v1)):
			temp += v1[i] - 1
		if k <= temp:
			return len(v1)
		else:
			k = k - temp
			ans = len(v1)
			while k:
				ans -= 1
				k -= 1
			return ans


class Solution:

	def maxTripletSum(self, arr, n, k):
		freq_num = {}
		has_duplicate = set()
		for num in arr:
			freq_num[num] = freq_num.get(num, 0) + 1
			if freq_num[num] > 1:
				has_duplicate.add(num)
		removable = 0
		for num in has_duplicate:
			removable += freq_num[num] - 1
		if removable >= k:
			return len(freq_num)
		return len(freq_num) - k + removable


from heapq import *

class Solution:

	def maxTripletSum(self, arr, n, K):
		max_heap = []
		d = {}
		for i in arr:
			if i in d:
				d[i] += 1
			else:
				d[i] = 1
		for i in d:
			heappush(max_heap, [-d[i], i])
		for i in range(K):
			(a, b) = heappop(max_heap)
			a = a + 1
			if a != 0:
				heappush(max_heap, [a, b])
		return len(max_heap)


class Solution:

	def maxTripletSum(self, a, n, k):
		d = dict()
		for i in range(n):
			d[a[i]] = d.get(a[i], 0) + 1
		ans = 0
		l = len(d)
		for x in d:
			ans += d[x]
		ans = min(l, abs(ans - k))
		return ans


from collections import Counter
import heapq

class Solution:

	def maxTripletSum(self, arr, n, k):
		mp = Counter(arr)
		l = []
		for i in mp.keys():
			heapq.heappush(l, (-mp[i], -i))
		i = 0
		while i < k:
			c = heapq.heappop(l)
			(c1, c2) = (-c[0], -c[1])
			c1 -= 1
			if c1 != 0:
				heapq.heappush(l, (-c1, -c2))
			i += 1
		return len(l)


import heapq

class Solution:

	def maxTripletSum(self, arr, n, K):
		d = {}
		for i in arr:
			if i not in d:
				d[i] = 1
			else:
				d[i] += 1
		heap = []
		for (i, j) in d.items():
			heapq.heappush(heap, [-j, -i])
		res = 0
		while K:
			K -= 1
			temp = heap[0]
			heapq.heappop(heap)
			if temp[0] * -1 > 1:
				temp[0] += 1
				heapq.heappush(heap, temp)
		return len(heap)


class Solution:

	def maxTripletSum(self, arr, n, K):
		s = set(arr)
		return min(len(s), n - K)


class Solution:

	def maxTripletSum(self, arr, n, K):
		di = dict()
		for i in arr:
			di[i] = di.get(i, 0) + 1
		extra = 0
		for i in di:
			extra += di[i] - 1 if di[i] > 1 else 0
		if K <= extra:
			return len(di)
		else:
			K -= extra
			return len(di) - K


class Solution:

	def maxTripletSum(self, arr, n, K):
		intFrequency = {}
		k = K
		for num in arr:
			if num not in intFrequency:
				intFrequency[num] = 0
			intFrequency[num] += 1
		from heapq import heappop, heappush
		minheap = []
		for key in intFrequency:
			if intFrequency[key] >= 2:
				heappush(minheap, (intFrequency[key], key))
		while minheap and k != 0:
			(count, key) = heappop(minheap)
			while count != 1 and k != 0:
				count -= 1
				k -= 1
				intFrequency[key] -= 1
		if k > 0:
			maxheap = []
			for key in intFrequency:
				heappush(maxheap, (-intFrequency[key], key))
			while maxheap and k > 0:
				(count, key) = heappop(maxheap)
				count *= -1
				while count > 0 and k > 0:
					count -= 1
					k -= 1
					intFrequency[key] -= 1
					if count == 0:
						intFrequency.pop(key)
		return len(intFrequency)


from collections import Counter

class Solution:

	def maxTripletSum(self, arr, n, K):
		a = len(list(set(arr)))
		d = n - a
		if K <= d:
			return a
		else:
			j = d - K
			return a + j


import heapq

class Solution:

	def maxTripletSum(self, arr, n, K):
		d = {}
		for item in arr:
			if item in d:
				d[item] += 1
			else:
				d[item] = 1
		s = []
		for k in d:
			s.append(d[k])
		s = [-i for i in s]
		heapq.heapify(s)
		while K > 0:
			temp = heapq.heappop(s)
			temp += 1
			if temp != 0:
				heapq.heappush(s, temp)
			K -= 1
		return len(s)


from collections import defaultdict as df
import heapq as h

class Solution:

	def maxTripletSum(self, arr, n, K):
		d = df(int)
		for i in arr:
			d[i] += 1
		l = [(d[i] * -1, i) for i in d]
		h.heapify(l)
		for i in range(K):
			(val, s) = h.heappop(l)
			val += 1
			h.heappush(l, (val, s)) if val != 0 else None
		return len(l)


class Solution:

	def maxTripletSum(self, arr, n, K):
		s = list(set(arr))
		m = len(s)
		rem = n - m
		if K < rem:
			return m
		elif K == rem:
			return m
		else:
			return m - (K - rem)


class Solution:

	def maxTripletSum(self, arr, n, K):
		freqs = {}
		for i in range(n):
			if arr[i] not in freqs:
				freqs[arr[i]] = 1
			else:
				freqs[arr[i]] += 1
		Sum = 0
		for val in freqs.values():
			Sum += val - 1
		Len = len(freqs)
		if K <= Sum:
			return Len
		else:
			K = K - Sum
			return Len - K


import heapq

class Solution:

	def maxTripletSum(self, arr, n, k):
		res = {}
		for num in arr:
			if num in res:
				res[num] += 1
			else:
				res[num] = 1
		ans = []
		for ele in res:
			heapq.heappush(ans, (-1 * res[ele], ele))
		while k:
			(freq, ele) = heapq.heappop(ans)
			freq += 1
			if freq:
				heapq.heappush(ans, (freq, ele))
			k -= 1
		return len(ans)


import heapq

class Solution:

	def maxTripletSum(self, arr, n, k):
		freq = dict()
		for element in arr:
			freq[element] = freq.get(element, 0) + 1
		maxHeap = []
		heapq.heapify(maxHeap)
		for (key, val) in freq.items():
			heapq.heappush(maxHeap, (-val, key))
		while k and maxHeap:
			pair = heapq.heappop(maxHeap)
			(val, key) = (-pair[0], pair[1])
			val -= 1
			if val > 0:
				heapq.heappush(maxHeap, (-val, key))
			k -= 1
		return len(maxHeap)


from heapq import heapify, heappush, heappop
from collections import Counter

class Solution:

	def maxTripletSum(self, arr, n, K):
		heap = []
		heapify(heap)
		hashMap = Counter(arr)
		for (key, value) in hashMap.items():
			heappush(heap, -1 * value)
		for _ in range(K):
			freq = abs(heappop(heap))
			if freq > 1:
				heappush(heap, -1 * (freq - 1))
		return len(heap)


class Solution:

	def maxTripletSum(self, arr, n, K):
		dis_cnt = len(set(arr))
		dif = n - dis_cnt
		if K <= dif:
			return dis_cnt
		else:
			return n - K


class Solution:

	def maxTripletSum(self, arr, n, K):
		d_eles = {arr[i]: 0 for i in range(n)}
		for i in range(n):
			if d_eles[arr[i]] == 0:
				d_eles[arr[i]] = 1
			else:
				K = K - 1
		return len(d_eles) - max(K, 0)


from collections import defaultdict

class MinHeap:

	def __init__(self):
		self.array = []
		self.length = 0

	def insert(self, num):
		self.array.append(num)
		self.length += 1
		child = self.length - 1
		parent = (child - 1) // 2
		while parent >= 0 and self.array[child] > self.array[parent]:
			(self.array[child], self.array[parent]) = (self.array[parent], self.array[child])
			child = parent
			parent = (child - 1) // 2

	def pop(self):
		result = self.array[0]
		self.array[0] = self.array[-1]
		self.array.pop()
		self.length -= 1
		parent = 0
		child = 1
		while child < self.length:
			if child + 1 < self.length and self.array[child + 1] > self.array[child]:
				child += 1
			if self.array[child] > self.array[parent]:
				(self.array[child], self.array[parent]) = (self.array[parent], self.array[child])
				parent = child
				child = 2 * child + 1
			else:
				break
		return result

	def peak(self):
		return self.array[0]

	def setPeak(self, num):
		self.array[0][0] = num

class Solution:

	def maxTripletSum(self, arr, n, K):
		minHeap = MinHeap()
		frequency = defaultdict(int)
		for num in arr:
			frequency[num] += 1
		for num in frequency:
			minHeap.insert([frequency[num], num])
		count = 0
		while minHeap.array and count < K:
			if minHeap.peak()[0] != 1:
				minHeap.setPeak(minHeap.peak()[0] - 1)
				count += 1
			else:
				minHeap.pop()
		if count == K:
			return len(frequency)
		else:
			return len(frequency) - (K - count)


class Solution:

	def maxTripletSum(self, arr, n, k):
		s = set(arr)
		diff = k - (n - len(s))
		if diff < 0:
			return len(s)
		else:
			return len(s) - diff


import heapq

class Solution:

	def maxTripletSum(self, arr, n, K):
		if K > len(arr):
			return 0
		minHeap = []
		counts = {}
		for num in arr:
			counts[num] = counts.get(num, 0) + 1
		distinct = 0
		for (num, freq) in counts.items():
			distinct += 1
			if freq > 1:
				heapq.heappush(minHeap, freq)
		while len(minHeap) > 0 and K > 0:
			K -= heapq.heappop(minHeap) - 1
		if K > 0:
			distinct -= K
		return distinct


class Solution:

	def maxTripletSum(self, arr, n, K):
		s = set()
		l = 0
		d = 0
		for i in range(n):
			v = arr[i]
			s.add(v)
			if len(s) > l:
				l = len(s)
				d += 1
		return min(n - K, d)


class Solution:

	def maxTripletSum(self, arr, n, K):
		distinct_els = set()
		for el in arr:
			if not el in distinct_els:
				distinct_els.add(el)
			else:
				K -= 1
		return len(distinct_els) - max(0, K)


class Solution:

	def maxTripletSum(self, arr, n, K):
		s = set(arr)
		if n - len(s) == K or n - len(s) > K:
			return len(s)
		else:
			return n - K