Given a array of N numbers, we need to maximize the sum of selected numbers. At each step, you need to select a number A_{i}, delete one occurrence of A_{i}-1 (if exists), and A_{i} each from the array. Repeat these steps until the array gets empty. The problem is to maximize the sum of the selected numbers.
Note: Numbers need to be selected from maximum to minimum.
Example 1:
Input : arr[ ] = {1, 2, 2, 2, 3, 4}
Output : 10
Explanation:
We select 4, so 4 and 3 are deleted leaving us with {1,2,2,2}.
Then we select 2, so 2 & 1 are deleted. We are left with{2,2}.
We select 2 in next two steps, thus the sum is 4+2+2+2=10.
Example 2:
Input : arr[ ] = {1, 2, 3} 
Output :  4
Explanation: We select 3, so 3 and 2 are deleted leaving us with {1}. Then we select 1, 0 doesn't exist so we delete 1. thus the sum is 3+1=4.
 
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 maximizeSum() that takes an array (arr), sizeOfArray (n), and return the maximum sum of the selected numbers. The driver code takes care of the printing.
Expected Time Complexity: O(NlogN).
Expected Auxiliary Space: O(N).
Constraints:
1 ≤ N ≤ 10^{5}
1 ≤ A[i] ≤ 10^{5}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Data structures

Starter code: #User function Template for python3



class Solution:

    

    def maximizeSum (self,arr, n) : 

        #Complete the function



Solutions:
from collections import defaultdict

class Solution:

	def maximizeSum(self, arr, n):
		ans = defaultdict(int)
		a = [False] * n
		sumi = 0
		for i in arr:
			ans[i] += 1
		for i in range(n - 1, -1, -1):
			if a[i] == False:
				a[i] = True
				sumi += arr[i]
				if ans[arr[i] - 1] > 0:
					a[i - ans[arr[i]]] = True
					ans[arr[i] - 1] -= 1
		return sumi


class Solution:

	def maximizeSum(self, arr, n):
		hash = {}
		for i in range(n - 1, -1, -1):
			if arr[i] in hash:
				hash[arr[i]] += 1
			else:
				hash[arr[i]] = 1
		res = 0
		for key in range(100000, 0, -1):
			if key in hash and hash[key] > 0:
				res += key * hash[key]
				if key - 1 in hash and hash[key - 1] > 0:
					hash[key - 1] -= min(hash[key], hash[key - 1])
				hash[key] = 0
		return res


from collections import defaultdict

class Solution:

	def maximizeSum(self, arr, n):
		total_sum = 0
		ha = defaultdict(int)
		for i in range(n - 1, -1, -1):
			ha[arr[i]] += 1
		for i in range(n - 1, -1, -1):
			if arr[i] in ha:
				total_sum += arr[i]
				ha[arr[i]] -= 1
				if ha[arr[i]] == 0:
					ha.pop(arr[i])
				if arr[i] - 1 in ha:
					ha[arr[i] - 1] -= 1
					if ha[arr[i] - 1] == 0:
						ha.pop(arr[i] - 1)
		return total_sum


class Solution:

	def maximizeSum(self, a, n):
		a.sort()
		d = {}
		for i in range(n):
			if a[i] not in d.keys():
				d[a[i]] = 1
			else:
				d[a[i]] += 1
		ans = 0
		for i in range(n - 1, -1, -1):
			if a[i] in d.keys():
				ans += a[i]
				d[a[i]] -= 1
				if d[a[i]] == 0:
					del d[a[i]]
				if a[i] - 1 in d.keys():
					d[a[i] - 1] -= 1
					if d[a[i] - 1] == 0:
						del d[a[i] - 1]
			if len(d) == 0:
				return ans


class Solution:

	def maximizeSum(self, arr, n):
		m = [0] * 100001
		for x in arr:
			m[x] += 1
		sumi = 0
		for i in range(n - 1, -1, -1):
			curr = arr[i]
			if m[curr] != 0:
				sumi += curr
				m[curr] -= 1
				if m[curr - 1] != 0:
					m[curr - 1] -= 1
		return sumi


from collections import defaultdict

class Solution:

	def maximizeSum(self, arr, n):
		s = 0
		x = defaultdict(int)
		for i in range(n - 1, -1, -1):
			x[arr[i]] += 1
		for i in range(n - 1, -1, -1):
			if arr[i] in x:
				s += arr[i]
				x[arr[i]] -= 1
				if x[arr[i]] == 0:
					x.pop(arr[i])
				if arr[i] - 1 in x:
					x[arr[i] - 1] -= 1
				if x[arr[i] - 1] == 0:
					x.pop(arr[i] - 1)
		return s


class Solution:

	def maximizeSum(self, arr, n):
		arr.sort()
		maxsum = 0
		index = n - 1
		mapping = {}
		for item in arr:
			if item not in mapping:
				mapping[item] = 1
			else:
				mapping[item] += 1
		while index >= 0:
			ai = arr[index]
			aj = ai - 1
			if ai in mapping:
				if mapping[ai] > 0:
					mapping[ai] -= 1
					maxsum += ai
					if aj in mapping:
						if mapping[aj] > 0:
							mapping[aj] -= 1
			index -= 1
		return maxsum


import sys

class Solution:

	def maximizeSum(self, arr, n):
		nb = dict()
		s = 0
		for i in range(n):
			if arr[i] in nb:
				nb[arr[i]] += 1
			else:
				nb[arr[i]] = 1
		for i in range(n - 1, -1, -1):
			if nb[arr[i]] > 0:
				s += arr[i]
				nb[arr[i]] -= 1
				if arr[i] - 1 in nb and nb[arr[i] - 1] > 0:
					nb[arr[i] - 1] -= 1
		return s


class Solution:

	def maximizeSum(self, arr, n):
		ans = 0
		a = [0] * arr[-1]
		for i in arr:
			a[i - 1] += 1
		a = a[::-1]
		for (i, j) in enumerate(a):
			ans += (len(a) - i) * j
			if i < len(a) - 1:
				x = a[i + 1] - a[i]
				if x > 0:
					a[i + 1] = x
				else:
					a[i + 1] = 0
		return ans


class Solution:

	def maximizeSum(self, arr, n):
		size = 10 ** 5 + 1
		count = [0] * size
		select = 0
		for i in range(n):
			count[arr[i]] += 1
		for i in range(size - 1, -1, -1):
			if count[i] > 0:
				select += i * count[i]
				if count[i - 1] > 0:
					count[i - 1] = count[i - 1] - count[i]
		return select


from collections import OrderedDict

class Solution:

	def maximizeSum(self, arr, n):
		arr = arr[::-1]
		od = dict()
		for elt in arr:
			if elt not in od:
				od[elt] = 0
			od[elt] += 1
		s = 0
		for i in range(n):
			if od[arr[i]] == 0:
				continue
			od[arr[i]] -= 1
			s += arr[i]
			if arr[i] - 1 in od and od[arr[i] - 1] > 0:
				od[arr[i] - 1] -= 1
		return s


from collections import defaultdict
from collections import OrderedDict

class Solution:

	def maximizeSum(self, arr, n):
		arr.sort(reverse=True)
		ans = 0
		i = 0
		d = defaultdict(int)
		for i in arr:
			d[i] += 1
		d1 = OrderedDict(sorted(d.items(), reverse=True))
		for (item, val) in d1.items():
			if val == 0:
				continue
			ans += item * val
			if item - 1 in d1:
				cnt = 0
				while d1[item - 1] != 0 and val != cnt:
					d1[item - 1] -= 1
					cnt += 1
			val = 0
		return ans


class Solution:

	def maximizeSum(self, arr, n):
		ans = dict.fromkeys(range(0, max(arr) + 1), 0)
		for i in range(n):
			ans[arr[i]] += 1
		result = 0
		i = max(arr)
		while i > 0:
			if ans[i] > 0:
				result += i
				ans[i - 1] -= 1
				ans[i] -= 1
			else:
				i -= 1
		return result


class Solution:

	def maximizeSum(self, arr, n):
		ans = 0
		di = dict()
		for i in arr:
			di[i] = di.get(i, 0) + 1
		arr = sorted(list(set(arr)))
		n = len(arr)
		for i in range(n - 1, -1, -1):
			if di[arr[i]] > 0:
				ans += di[arr[i]] * arr[i]
				if arr[i] - 1 in di:
					di[arr[i] - 1] -= min(di[arr[i] - 1], di[arr[i]])
		return ans


class Solution:

	def maximizeSum(self, arr, n):
		arr.sort()
		ans = 0
		while len(arr) > 0:
			el = arr.pop(-1)
			s = el
			l = len(arr) - 1
			while l >= 0 and arr[l] == el:
				l -= 1
			if l >= 0 and arr[l] == el - 1:
				arr.pop(l)
			ans += el
		return ans


class Solution:

	def maximizeSum(self, arr, n):
		maP = {}
		for i in arr:
			if i in maP:
				maP[i] += 1
			else:
				maP[i] = 1
		Sum = 0
		for i in arr[::-1]:
			if maP[i]:
				Sum += i
				maP[i] -= 1
				if i - 1 in maP and maP[i - 1]:
					maP[i - 1] -= 1
		return Sum


from collections import *

class Solution:

	def maximizeSum(self, a, n):
		d = defaultdict(int)
		for i in a:
			d[i] += 1
		val = list(d.keys())
		val.sort(reverse=True)
		i = 0
		ln = len(val)
		ans = 0
		while i < ln:
			ans += val[i]
			d[val[i]] -= 1
			if val[i] - 1 in d:
				d[val[i] - 1] -= 1
			while i < ln and d[val[i]] <= 0:
				i += 1
		return ans


import heapq

class Solution:

	def maximizeSum(self, arr, n):
		dp = {}
		for i in range(len(arr)):
			if arr[i] in dp:
				dp[arr[i]] += 1
			else:
				dp[arr[i]] = 1
		newar = []
		for (num, freq) in dp.items():
			newar.append([-num, freq])
		nuk = len(newar)
		heapq.heapify(newar)
		numbe = 0
		while nuk > 1:
			a = heapq.heappop(newar)
			b = heapq.heappop(newar)
			nuk -= 2
			numbe += -1 * a[0] * a[1]
			notb = False
			if a[0] + 1 == b[0]:
				if b[1] - a[1] > 0:
					heapq.heappush(newar, [b[0], b[1] - a[1]])
					nuk += 1
			else:
				heapq.heappush(newar, b.copy())
				nuk += 1
		if len(newar):
			numbe += -1 * newar[0][0] * newar[0][1]
		return numbe


class Solution:

	def maximizeSum(self, arr, n):
		ans = 0
		freq = {}
		for i in arr:
			try:
				freq[i] += 1
			except:
				freq[i] = 1
		for i in range(n - 1, -1, -1):
			if freq[arr[i]] > 0:
				ans += arr[i]
				freq[arr[i]] -= 1
				try:
					freq[arr[i] - 1] -= 1
				except:
					continue
		return ans


class Solution:

	def maximizeSum(self, arr, n):
		Max = max(arr)
		count = [0 for i in range(Max + 1)]
		for i in range(len(arr)):
			count[arr[i]] += 1
		Sum = 0
		for i in range(len(count) - 1, 0, -1):
			while count[i] > 0 and count[i - 1] > 0:
				Sum += i
				count[i] -= 1
				count[i - 1] -= 1
			if count[i - 1] == 0:
				Sum += i * count[i]
		return Sum


class Solution:

	def maximizeSum(self, arr, n):
		d = dict()
		arr.sort()
		for i in range(n):
			if arr[i] not in d:
				d[arr[i]] = 1
			else:
				d[arr[i]] += 1
		s = 0
		for i in range(n - 1, -1, -1):
			if d[arr[i]] > 0:
				s += arr[i]
				d[arr[i]] -= 1
				if arr[i] - 1 in d:
					d[arr[i] - 1] -= 1
		return s


class Solution:

	def maximizeSum(self, arr, n):
		array = [0] * 100001
		for i in arr:
			array[i] += 1
		sumLet = 0
		for j in range(n - 1, -1, -1):
			crrunt = arr[j]
			if array[crrunt] != 0:
				sumLet += crrunt
				array[crrunt] -= 1
				if array[crrunt - 1] != 0:
					array[crrunt - 1] -= 1
		return sumLet


class Solution:

	def maximizeSum(self, arr, n):
		sum = 0
		maxi = max(arr)
		dict1 = dict.fromkeys(range(0, maxi + 1), 0)
		for i in range(n):
			dict1[arr[i]] += 1
		i = maxi
		while i > 0:
			if dict1[i] > 0:
				sum = sum + i
				dict1[i - 1] = dict1[i - 1] - 1
				dict1[i] -= 1
			else:
				i = i - 1
		return sum


class Solution:

	def maximizeSum(self, arr, n):
		arr.sort(reverse=True)
		d = {}
		for i in arr:
			if i not in d:
				d[i] = 1
			else:
				d[i] += 1
		s = 0
		for i in range(n):
			if d[arr[i]] > 0:
				d[arr[i]] -= 1
				s += arr[i]
				if arr[i] - 1 in d and d[arr[i] - 1] > 0:
					d[arr[i] - 1] -= 1
		return s


from collections import defaultdict

class Solution:

	def bins(self, arr, k, u):
		(low, high) = (0, u)
		while low <= high:
			mid = (low + high) // 2
			if arr[mid] == k:
				return True
			elif arr[mid] > k:
				high = mid - 1
			elif arr[mid] < k:
				low = mid + 1
		return False

	def maximizeSum(self, arr, n):
		dict1 = defaultdict(int)
		for i in arr:
			dict1[i] += 1
		(k, ans) = (sorted(list(dict1.keys())), 0)
		u = len(k)
		for i in range(len(k) - 1, -1, -1):
			h1 = k[i]
			if self.bins(k, h1 - 1, u):
				temp = min(dict1[h1], dict1[h1 - 1])
				ans += h1 * temp
				dict1[h1] -= temp
				dict1[h1 - 1] -= temp
				if dict1[h1] == 0:
					del dict1[h1]
				if dict1[h1 - 1] == 0:
					del dict1[h1 - 1]
		for j in dict1:
			ans += j * dict1[j]
		return ans


from collections import Counter

class Solution:

	def maximizeSum(self, arr, n):
		maxSum = 0
		d = Counter(arr)
		for i in arr[::-1]:
			elem = i
			if d[elem] > 0:
				maxSum += elem
				d[elem] -= 1
				if elem - 1 in d:
					d[elem - 1] -= 1
		return maxSum


from collections import Counter

class Solution:

	def maximizeSum(self, arr, n):
		c = Counter(arr)
		t = sorted(set(arr), reverse=True)
		tot = 0
		for i in range(len(t)):
			tot += t[i] * c[t[i]]
			if t[i] - 1 in c:
				c[t[i] - 1] = c[t[i] - 1] - min(c[t[i]], c[t[i] - 1])
		return tot


class Solution:

	def maximizeSum(self, arr, n):
		d = {}
		for i in range(n):
			if arr[i] in d:
				d[arr[i]].append(i)
			else:
				d[arr[i]] = [i]
		ans = 0
		while len(arr) != 0:
			temp = arr.pop()
			if len(d[temp]) != 0:
				d[temp].pop()
				ans = ans + temp
				if temp - 1 in d and len(d[temp - 1]) != 0:
					d[temp - 1].pop()
		return ans


class Solution:

	def maximizeSum(self, arr, n):
		a = [0] * (max(arr) + 1)
		ans = 0
		for r in arr:
			a[r] += 1
		for i in range(max(arr), 0, -1):
			if a[i] > 0:
				ans += i * a[i]
				a[i - 1] -= a[i]
		return ans


class Solution:

	def maximizeSum(self, arr, n):
		lst = [0] * 1000001
		for i in arr:
			lst[i] += 1
		n_sum = 0
		for i in range(n - 1, -1, -1):
			maxi = arr[i]
			if lst[maxi] != 0:
				n_sum += maxi
				lst[maxi] -= 1
				if lst[maxi - 1] != 0:
					lst[maxi - 1] -= 1
		return n_sum


class Solution:

	def maximizeSum(self, arr, n):
		arr.sort()
		cur_sum = 0
		dic = {}
		for i in arr:
			dic[i] = dic.get(i, 0) + 1
		while arr:
			num1 = arr.pop()
			if dic.get(num1, 0) == 0:
				continue
			dic[num1] -= 1
			cur_sum += num1
			if dic.get(num1 - 1, 0) > 0:
				dic[num1 - 1] -= 1
		return cur_sum


class Solution:

	def maximizeSum(self, arr, n):
		dict = {}
		for num in arr:
			if num in dict:
				dict[num] += 1
			else:
				dict[num] = 1
		answer = 0
		for i in range(len(arr) - 1, -1, -1):
			if dict[arr[i]] > 0:
				dict[arr[i]] -= 1
				answer += arr[i]
				num = arr[i] - 1
				if num in dict and dict[num] > 0:
					dict[num] -= 1
		return answer


class Solution:

	def maximizeSum(self, a, n):
		a.sort(reverse=True)
		d = {}
		s = 0
		l = []
		for i in a:
			if i in d:
				d[i] += 1
			else:
				l.append(i)
				d[i] = 1
		for j in l:
			while d[j] != 0:
				s += j
				d[j] -= 1
				if j - 1 in d and d[j - 1] != 0:
					d[j - 1] -= 1
		return s


class Solution:

	def maximizeSum(self, arr, n):
		arr.sort()
		ans = 0
		Dict = {}
		for e in arr:
			try:
				Dict[e] += 1
			except:
				Dict[e] = 1
		arr.reverse()
		for e in arr:
			if Dict[e] > 0:
				ans += e
				Dict[e] -= 1
				try:
					if Dict[e - 1] > 0:
						Dict[e - 1] -= 1
				except:
					pass
		return ans


from collections import Counter

class Solution:

	def maximizeSum(self, arr, n):
		arr.sort()
		di = Counter(arr)
		sum = 0
		for i in range(n - 1, -1, -1):
			if di[arr[i]]:
				sum += arr[i]
				if di.get(arr[i] - 1):
					di[arr[i] - 1] -= 1
					di[arr[i]] -= 1
				else:
					di[arr[i]] -= 1
		return sum


class Solution:

	def maximizeSum(self, arr, n):
		dict = {}
		count = 0
		for i in arr:
			if i in dict:
				dict[i] += 1
			else:
				dict[i] = 1
		for i in range(n - 1, -1, -1):
			if dict[arr[i]] > 0:
				count += arr[i]
				dict[arr[i]] -= 1
				if arr[i] - 1 in dict:
					dict[arr[i] - 1] -= 1
		return count


class Solution:

	def maximizeSum(self, arr, n):
		s = 0
		d = {}
		s = 0
		while n > 0:
			i = arr[n - 1]
			if i in d:
				d[i] += 1
			else:
				d[i] = 1
			s += i
			if i + 1 in d and d[i + 1] > 0:
				d[i + 1] -= 1
				d[i] -= 1
				s -= i
			n -= 1
		return s


class Solution:

	def maximizeSum(self, arr, n):
		dict = {}
		for num in arr:
			dict[num] = dict.get(num, 0) + 1
		res = 0
		sorted_keys = sorted(dict.keys())
		for key in sorted_keys[::-1]:
			if key - 1 in dict.keys():
				res += dict[key] * key
				dict[key - 1] -= dict[key]
				if dict[key - 1] < 0:
					dict[key - 1] = 0
				dict[key] = 0
			else:
				res += dict[key] * key
				dict[key] = 0
		for key in dict.keys():
			res += dict[key] * key
		return res


from collections import Counter

class Solution:

	def maximizeSum(self, arr, n):
		arr.sort()
		res = 0
		hSet = Counter(arr)
		for i in range(n - 1, -1, -1):
			if not hSet[arr[i]]:
				continue
			res += arr[i]
			hSet[arr[i]] -= 1
			if hSet[arr[i] - 1]:
				hSet[arr[i] - 1] -= 1
		return res


class Solution:

	def maximizeSum(self, arr, n):
		sz = max(arr) + 1
		m = [0] * sz
		for x in arr:
			m[x] += 1
		sumi = 0
		for i in range(n - 1, -1, -1):
			curr = arr[i]
			if m[curr] > 0:
				sumi += curr
				m[curr] -= 1
				if curr - 1 >= -1 and m[curr - 1] != 0:
					m[curr - 1] -= 1
		return sumi


from collections import Counter

class Solution:

	def maximizeSum(self, arr, n):
		a = dict(Counter(arr))
		sum = 0
		for i in range(n - 1, -1, -1):
			if arr[i] in a and a[arr[i]] > 0:
				b = arr[i]
				sum += b
				a[b] -= 1
				if b - 1 in a:
					a[b - 1] -= 1
		return sum


class Solution:

	def maximizeSum(self, arr, n):
		sum = 0
		i = n - 1
		ready = True
		prev_val = None
		prev_count = 0
		while i > -1:
			if prev_val == None:
				sum += arr[i]
				prev_val = arr[i]
				prev_count = 1
			elif prev_val > arr[i] + 1:
				sum += arr[i]
				prev_val = arr[i]
				prev_count = 1
			elif prev_val == arr[i] + 1:
				if prev_count > 0:
					prev_count = prev_count - 1
				else:
					sum += arr[i]
					prev_val = arr[i]
					prev_count = 1
			elif prev_val == arr[i]:
				sum += arr[i]
				prev_count += 1
			else:
				prev_val = prev_val
			i = i - 1
		return sum


class Solution:

	def maximizeSum(self, arr, n):
		sum = 0
		i = n - 1
		ready = True
		deletion = {}
		while i > -1:
			if arr[i] not in deletion or deletion[arr[i]] == 0:
				sum += arr[i]
				if arr[i] - 1 in deletion:
					deletion[arr[i] - 1] = deletion[arr[i] - 1] + 1
				else:
					deletion[arr[i] - 1] = 1
			else:
				deletion[arr[i]] = deletion[arr[i]] - 1
			i = i - 1
		return sum


class Solution:

	def maximizeSum(self, arr, n):
		dic = {}
		for i in range(n):
			if arr[i] in dic:
				dic[arr[i]] += 1
			else:
				dic[arr[i]] = 1
		su = 0
		j = n - 1
		arr.sort()
		while j >= 0:
			if dic[arr[j]] > 0:
				su += arr[j]
				dic[arr[j]] -= 1
				if arr[j] - 1 in dic:
					dic[arr[j] - 1] -= 1
			j -= 1
		return su


from collections import Counter

class Solution:

	def maximizeSum(self, arr, n):
		u = 0
		brr = Counter(arr)
		v = list(brr.keys())
		v.sort(reverse=True)
		for i in v:
			if i - 1 in brr:
				if brr[i] >= brr[i - 1]:
					u += brr[i] * i
					brr[i] = 0
					brr[i - 1] = 0
				else:
					u += brr[i] * i
					brr[i - 1] = brr[i - 1] - brr[i]
					brr[i] = 0
			else:
				u += brr[i] * i
				brr[i] = 0
		return u


class Solution:

	def maximizeSum(self, array, n):
		dictionary = dict()
		for number in array:
			if number in dictionary:
				dictionary[number] += 1
			else:
				dictionary[number] = 1
		keys = list(dictionary.keys())
		keys.sort()
		keys.reverse()
		result = 0
		for key in keys:
			if dictionary[key] > 0:
				result += key * dictionary[key]
				if key - 1 in keys:
					dictionary[key - 1] -= dictionary[key]
		return result


class Solution:

	def maximizeSum(self, arr, n):
		summ = 0
		map = [0] * 99999
		for num in arr:
			map[num] += 1
		for i in range(len(arr) - 1, -1, -1):
			if map[arr[i]] != 0:
				summ += arr[i]
				map[arr[i]] -= 1
				if map[arr[i] - 1] != 0:
					map[arr[i] - 1] -= 1
		return summ


class Solution:

	def maximizeSum(self, a, n):
		d = {}
		for i in a:
			d[i] = 0
		for i in a:
			d[i] += 1
		temp = 0
		for i in range(n - 1, -1, -1):
			if d[a[i]] > 0:
				temp += a[i]
				d[a[i]] -= 1
				try:
					d[a[i] - 1] -= 1
				except:
					pass
		return temp


class Solution:

	def maximizeSum(self, arr, n):
		map = {}
		summ = 0
		i = 1
		for (idx, num) in enumerate(arr):
			if num in map:
				map[num] += 1
			else:
				map[num] = 1
		while i <= len(arr):
			key = arr[-i]
			if map[key] > 0:
				if key - 1 in map and map[key - 1] > 0:
					summ += key
					map[key] -= 1
					map[key - 1] -= 1
				else:
					summ += key
					map[key] -= 1
			i += 1
		return summ


from collections import defaultdict

class Solution:

	def maximizeSum(self, arr, n):
		seenAt = defaultdict(list)
		for (idx, el) in enumerate(arr):
			seenAt[el].append(idx)
		max_sum = 0
		for idx in range(n - 1, -1, -1):
			el = arr[idx]
			if el > 0:
				max_sum += el
				seenAt[el].pop()
				if el - 1 in seenAt and len(seenAt[el - 1]) > 0:
					arr[seenAt[el - 1].pop()] = 0
		return max_sum


from collections import Counter

class Solution:

	def maximizeSum(self, arr, n):
		s = 0
		arr.sort(reverse=True)
		d = dict(Counter(arr))
		for i in range(len(arr)):
			if arr[i] in d:
				s += arr[i]
				d[arr[i]] -= 1
				if d[arr[i]] == 0:
					del d[arr[i]]
				if arr[i] - 1 in d:
					d[arr[i] - 1] -= 1
					if d[arr[i] - 1] == 0:
						del d[arr[i] - 1]
		return s


class Solution:

	def maximizeSum(self, arr, n):
		temp = 0
		dict_ = {}
		for i in arr:
			if i not in dict_:
				dict_[i] = 1
			else:
				dict_[i] += 1
		for i in range(n - 1, -1, -1):
			if dict_[arr[i]] > 0:
				temp += arr[i]
				dict_[arr[i]] -= 1
				if arr[i] - 1 in dict_:
					dict_[arr[i] - 1] -= 1
		return temp


class Solution:

	def maximizeSum(self, arr, n):
		temp = [0] * 100001
		for i in arr:
			temp[i] += 1
		sm = 0
		for i in range(n - 1, -1, -1):
			curr = arr[i]
			if temp[curr]:
				sm += curr
				temp[curr] -= 1
				if temp[curr - 1]:
					temp[curr - 1] -= 1
		return sm