You are given an array arr of n integers. For each index i, you have to find the sum of all integers present in the array with a value less than arr[i].
Example 1:
Input:
n = 3
arr = {1, 2, 3}
Output:
0 1 3
Explanation:
For 1, there are no elements lesser than itself.
For 2, only 1 is lesser than 2.
And for 3, 1 and 2 are lesser than 3, so the sum is 3.
Example 2:
Input:
n = 2
arr = {4, 4}
Output:
0 0
Explanation:
For 4, there are no elements lesser than itself. 
For 4, there are no elements lesser than itself.
There are no smaller elements than 4.
Your Task:
You don't need to read input or print anything. Your task is to complete the function smallerSum() which takes an integer n and an array arr and returns an array of length n , the answer for every index.
Expected Time Complexity:O(n log n)
Expected Space Complexity:O(n)
Constraints:
1 <= n <= 10^{5}
0 <= arr[i] <= 10^{9}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Sorting

Data structures

Starter code: from typing import List





class Solution:

    def smallerSum(self, n : int, arr : List[int]) -> List[int]:

        # code here

        



Solutions:
from typing import List

class Solution:

	def smallerSum(self, n: int, arr: List[int]) -> List[int]:
		sorted_a = sorted(arr)
		smaller = {}
		prev_i = -1
		prev_a = 0
		summ = 0
		for (i, a) in enumerate(sorted_a):
			if a not in smaller:
				summ = summ + (i - prev_i) * prev_a
				smaller[a] = summ
				prev_a = a
				prev_i = i
		return [smaller[a] for a in arr]


from typing import List

class Solution:

	def smallerSum(self, n: int, arr: List[int]) -> List[int]:
		a = []
		sortArr = []
		for j in range(n):
			sortArr.append(arr[j])
		sortArr.sort()
		d = {}
		sum = 0
		for ele in sortArr:
			if ele not in d:
				d[ele] = sum
			sum += ele
		for i in range(n):
			a.append(d[arr[i]])
		return a


from typing import List

class Solution:

	def smallerSum(self, n: int, arr: List[int]) -> List[int]:
		a = arr.copy()
		a.sort()
		m = {}
		sum = 0
		for i in a:
			if i not in m:
				m[i] = sum
			sum = sum + i
		res = []
		for j in range(n):
			res.append(m[arr[j]])
		return res


from typing import List

class Solution:

	def smallerSum(self, n: int, arr: List[int]) -> List[int]:
		z = []
		for ele in arr:
			z.append(ele)
		z.sort()
		d = dict()
		s = 0
		for ele in z:
			if ele not in d:
				d[ele] = s
			s = s + ele
		ans = []
		for ele in arr:
			ans.append(d[ele])
		return ans


from typing import List

class Solution:

	def smallerSum(self, n: int, arr: List[int]) -> List[int]:
		d = dict()
		a = arr.copy()
		a.sort()
		s = 0
		ans = []
		for i in range(n):
			if a[i] not in d:
				d[a[i]] = s
			s += a[i]
		for i in arr:
			ans.append(d[i])
		return ans


from typing import List

class Solution:

	def smallerSum(self, n: int, arr: List[int]) -> List[int]:
		temp = arr.copy()
		temp.sort()
		ssum = [0] * n
		currSum = 0
		i = 0
		j = i + 1
		while i < n and j < n:
			if temp[i] == temp[j]:
				ssum[j] = currSum
			else:
				currSum += temp[i] * (j - i)
				ssum[j] = currSum
				i = j
			j += 1
		m = {}
		for i in range(0, n):
			m[temp[i]] = ssum[i]
		for i in range(0, n):
			ssum[i] = m[arr[i]]
		return ssum


from typing import List
import bisect

class Solution:

	def smallerSum(self, n: int, a: List[int]) -> List[int]:
		ans = [0] * n
		count = {}
		for i in a:
			count[i] = count.get(i, 0) + 1
		q = list(a)
		q.sort()
		s = [0] * n
		d = {}
		d[q[0]] = 0
		for i in range(1, n):
			s[i] = s[i - 1] + q[i - 1]
		for i in range(n):
			ind = bisect.bisect_left(q, a[i])
			ans[i] = s[ind]
		return ans


from typing import List

class Solution:

	def smallerSum(self, n: int, a: List[int]) -> List[int]:
		count = {}
		for i in a:
			count[i] = count.get(i, 0) + 1
		q = list(a)
		q.sort()
		s = [0] * n
		d = {}
		d[q[0]] = 0
		for i in range(1, n):
			if q[i - 1] == q[i]:
				s[i] = s[i - 1]
			else:
				s[i] = q[i - 1] * count[q[i - 1]] + s[i - 1]
			d[q[i]] = s[i]
		ans = [0] * n
		for i in range(n):
			ans[i] = d[a[i]]
		return ans


from typing import List

class Solution:

	def smallerSum(self, n: int, arr: List[int]) -> List[int]:
		l = arr[:]
		l.sort()
		from collections import defaultdict
		d = defaultdict(int)
		for i in range(len(l) - 1, -1, -1):
			d[l[i]] = i
		s = [0]
		for i in range(len(l)):
			s.append(s[-1] + l[i])
		ans = []
		for i in arr:
			ans.append(s[d[i]])
		return ans


from typing import List

class Solution:

	def smallerSum(self, n: int, arr: List[int]) -> List[int]:
		has1 = {}
		for i in arr:
			if i in has1:
				has1[i] += 1
			else:
				has1[i] = 1
		has = {}
		su = 0
		temp = sorted(set(arr))
		for i in temp:
			has[i] = su
			su += i * has1[i]
		ans = []
		for i in arr:
			ans.append(has[i])
		return ans


from typing import List

class Solution:

	def smallerSum(self, n: int, arr: List[int]) -> List[int]:
		a = arr.copy()
		a.sort()
		dic = {a[0]: 0}
		total = 0
		for i in range(1, n):
			total += a[i - 1]
			if a[i] not in dic:
				dic[a[i]] = total
		ans = []
		for elm in arr:
			ans.append(dic[elm])
		return ans


from typing import List
from collections import OrderedDict

class Solution:

	def smallerSum(self, n: int, arr: List[int]) -> List[int]:
		hashmap = {}
		ans = []
		arrcpy = arr.copy()
		arrcpy.sort()
		prefixSum = arrcpy[0]
		hashmap[arrcpy[0]] = 0
		for i in range(1, n):
			if arrcpy[i - 1] == arrcpy[i]:
				sum = hashmap[arrcpy[i - 1]]
				hashmap[arrcpy[i]] = sum
			else:
				hashmap[arrcpy[i]] = prefixSum
			prefixSum += arrcpy[i]
		for i in range(n):
			ans.append(hashmap[arr[i]])
		return ans


from typing import List

class Solution:

	def smallerSum(self, n: int, arr: List[int]) -> List[int]:
		d = {}
		ind = 0
		for i in arr:
			if i in d:
				d[i].append(ind)
			else:
				d[i] = [ind]
			ind += 1
		res = [0] * n
		prev = 0
		for i in sorted(d.keys()):
			for j in d[i]:
				res[j] = prev
			prev += i * len(d[i])
		return res


from typing import List
import copy

class Solution:

	def binarySearch(self, a, ele):
		i = 0
		j = len(a)
		while i < j:
			m = (i + j) // 2
			if a[m] < ele:
				i = m + 1
			else:
				j = m
		return i

	def smallerSum(self, n: int, arr: List[int]) -> List[int]:
		a = arr.copy()
		ans = [0] * n
		a.sort()
		l = [-1] * n
		k = 0
		l[0] = a[0]
		for i in range(1, n):
			l[i] = l[i - 1] + a[i]
		for i in arr:
			x = self.binarySearch(a, i)
			if x != 0:
				ans[k] = l[x - 1]
				k += 1
			else:
				k += 1
		return ans


from typing import List
from bisect import bisect_left, bisect_right

class Solution:

	def smallerSum(self, n: int, arr: List[int]) -> List[int]:
		tmp = []
		pre = []
		ans = []
		for i in range(n):
			tmp.append(arr[i])
		tmp.sort()
		pre = tmp[:]
		for i in range(1, n):
			pre[i] += pre[i - 1]
		for i in range(n):
			lb = bisect_left(tmp, arr[i])
			if lb == 0:
				ans.append(0)
			else:
				ans.append(pre[lb - 1])
		return ans


from typing import List

class Solution:

	def smallerSum(self, n: int, arr: List[int]) -> List[int]:
		arr_sorted = sorted(arr)
		initial = 0
		prefix_arr = []
		for i in arr_sorted:
			initial += i
			prefix_arr.append(initial)
		dct = {}
		for i in range(len(arr_sorted)):
			if arr_sorted[i] not in dct:
				dct[arr_sorted[i]] = prefix_arr[i] - arr_sorted[i]
		output = []
		for i in arr:
			output.append(dct[i])
		return output


from typing import List

class Solution:

	def smallerSum(self, n: int, arr: List[int]) -> List[int]:
		l = list(arr)
		l.sort()
		prefix = {}
		sum_ = 0
		for i in l:
			if i not in prefix:
				prefix[i] = sum_
			sum_ += i
		res = []
		for i in range(n):
			res.append(prefix[arr[i]])
		return res


from typing import List
import bisect

class Solution:

	def smallerSum(self, n: int, arr: List[int]) -> List[int]:
		result = []
		sorted_arr = sorted(arr)
		rolling_sum_of_sorted_arr = [0]
		for i in range(1, n):
			rolling_sum_of_sorted_arr.append(rolling_sum_of_sorted_arr[i - 1] + sorted_arr[i - 1])
		for i in range(0, n):
			cur_ele_idx = bisect.bisect_left(sorted_arr, arr[i])
			summ = rolling_sum_of_sorted_arr[cur_ele_idx]
			result.append(summ)
		return result


from typing import List

class Solution:

	def smallerSum(self, n: int, arr: List[int]) -> List[int]:
		k = sorted(arr)
		d = {k[0]: 0}
		sum = k[0]
		for i in range(1, n):
			if k[i] != k[i - 1]:
				d[k[i]] = sum
			sum = sum + k[i]
		l = []
		for i in arr:
			l.append(d[i])
		return l


from bisect import bisect_left as lb

class Solution:

	def smallerSum(self, n, a):
		t = [(x, x) for x in a]
		t.append((0, 0))
		t.sort()
		for i in range(n):
			t[i + 1] = (t[i + 1][0], t[i + 1][1] + t[i][1])
		res = []
		for x in a:
			i = lb(t, (x, x))
			if i > 0:
				res.append(t[i - 1][1])
			else:
				res.append(0)
		return res


from typing import List

class Solution:

	def smallerSum(self, n: int, arr: List[int]) -> List[int]:
		t = list(arr)
		t.sort()
		a = {}
		b = []
		i = n - 1
		sum1 = sum(t)
		while i >= 0:
			sum1 -= t[i]
			a[t[i]] = sum1
			i -= 1
		for i in arr:
			b.append(a[i])
		return b


from typing import List
from bisect import bisect_left

class Solution:

	def smallerSum(self, n: int, arr: List[int]) -> List[int]:
		temp = []
		for i in arr:
			temp.append(i)
		temp.sort()
		d = {}
		d[temp[0]] = 0
		prev = temp[0]
		prev_count = 1
		count = 0
		for i in temp[1:]:
			if i == prev:
				prev_count += 1
				d[i] = count
			else:
				count += prev * prev_count
				d[i] = count
				prev = i
				prev_count = 1
		ans = []
		for i in arr:
			ans.append(d[i])
		return ans


from typing import List

class Solution:

	def smallerSum(self, n: int, arr: List[int]) -> List[int]:
		dct = {}
		for value in arr:
			dct[value] = dct.get(value, 0) + 1
		values = sorted([(key, item) for (key, item) in dct.items()])
		res = []
		subSum = 0
		resDct = {}
		for (value, kvantity) in values:
			resDct[value] = subSum
			subSum += value * kvantity
		return [resDct[value] for value in arr]


from typing import List

class Solution:

	def smallerSum(self, n: int, arr: List[int]) -> List[int]:
		k = arr + []
		arr.sort()
		newarr = [0]
		if arr == []:
			return arr
		currsum = arr[0]
		for i in range(1, n):
			if arr[i] == arr[i - 1]:
				newarr.append(newarr[-1])
			else:
				newarr.append(currsum)
			currsum += arr[i]
		d = {}
		for i in range(n):
			d[arr[i]] = newarr[i]
		for i in range(n):
			k[i] = d[k[i]]
		return k


from typing import List

class Solution:

	def mergeSort(self, l: List[int]) -> List[int]:
		if len(l) > 1:
			mid = len(l) // 2
			left = self.mergeSort(l[:mid])
			right = self.mergeSort(l[mid:])
			i = j = k = 0
			while i < len(left) and j < len(right):
				if left[i] < right[j]:
					l[k] = left[i]
					i += 1
				else:
					l[k] = right[j]
					j += 1
				k += 1
			while i < len(left):
				l[k] = left[i]
				i += 1
				k += 1
			while j < len(right):
				l[k] = right[j]
				j += 1
				k += 1
		return l

	def smallerSum(self, n: int, arr: List[int]) -> List[int]:
		final_list = [0] * n
		hash_map = {}
		for index in range(n):
			if arr[index] in hash_map:
				hash_map[arr[index]].append(index)
			else:
				hash_map[arr[index]] = [index]
		arr = self.mergeSort(list(set(arr)))
		the_sum = 0
		for num in arr:
			indices = hash_map[num]
			for i in indices:
				final_list[i] = the_sum
			the_sum += num * len(indices)
		return final_list


from typing import List

class Solution:

	def smallerSum(self, n: int, arr: List[int]) -> List[int]:
		final_list = [0] * n
		hash_map = {}
		for index in range(n):
			if arr[index] in hash_map:
				hash_map[arr[index]].append(index)
			else:
				hash_map[arr[index]] = [index]
		arr = sorted(set(arr))
		the_sum = 0
		for num in arr:
			indices = hash_map[num]
			for i in indices:
				final_list[i] = the_sum
			the_sum += num * len(indices)
		return final_list


from typing import List
from bisect import bisect_left, bisect_right

class Solution:

	def smallerSum(self, n: int, arr: List[int]) -> List[int]:
		ans = []
		listCopy = []
		prefixSum = []
		for i in range(n):
			listCopy.append(arr[i])
		listCopy.sort()
		prefixSum = listCopy[:]
		for i in range(1, n):
			prefixSum[i] += prefixSum[i - 1]
		for val in arr:
			index = bisect_left(listCopy, val)
			if index != 0:
				ans.append(prefixSum[index - 1])
			else:
				ans.append(0)
		return ans


from typing import List

class Solution:

	def smallerSum(self, n: int, arr: List[int]) -> List[int]:
		sum_dict = {}
		arr_sorted = sorted(arr)
		sum_dict[arr_sorted[0]] = 0
		curr_sum = arr_sorted[0]
		for num in arr_sorted[1:]:
			if num not in sum_dict:
				sum_dict[num] = curr_sum
			curr_sum += num
		l = []
		for num in arr:
			l.append(sum_dict[num])
		return l


from typing import List

class Solution:

	def smallerSum(self, n: int, arr: List[int]) -> List[int]:
		li = []
		nums = arr.copy()
		nums.sort()
		dic = {}
		sum1 = 0
		for i in range(n):
			if nums[i] not in dic:
				dic[nums[i]] = sum1
			sum1 += nums[i]
		for i in arr:
			li.append(dic[i])
		return li


from typing import List
from heapq import heappush, heappop
import bisect

class Solution:

	def smallerSum(self, n: int, arr: List[int]) -> List[int]:
		l = []
		hashmap = {}
		heap = []
		for ele in arr:
			hashmap[ele] = hashmap.get(ele, 0) + 1
		for ele in hashmap:
			heappush(heap, ele)
		sum = 0
		res = {}
		while heap:
			ele = heappop(heap)
			res[ele] = sum
			sum += hashmap[ele] * ele
		resultant = []
		for ele in arr:
			resultant.append(res[ele])
		return resultant


from typing import List

class Solution:

	def smallerSum(self, n: int, arr: List[int]) -> List[int]:
		brr = sorted(list(set(arr)))
		sums = dict()
		totals = dict()
		for i in arr:
			sums[i] = sums.get(i, 0) + i
		for i in range(1, len(brr)):
			totals[brr[i]] = totals.get(brr[i - 1], 0) + sums[brr[i - 1]]
		return [totals.get(i, 0) for i in arr]


from typing import List

class Solution:

	def smallerSum(self, n: int, arr: List[int]) -> List[int]:
		arr_ = sorted(arr)
		ans = 0
		dict_ = {}
		for i in arr_:
			if i not in dict_:
				dict_[i] = ans
			ans += i
		return [dict_[i] for i in arr]


from typing import List

class Solution:

	def smallerSum(self, n: int, arr: List[int]) -> List[int]:
		pos = []
		for i in range(len(arr)):
			pos.append([arr[i], i])
		arr.sort()
		pre = []
		pre.append(arr[0])
		t = arr[0]
		for i in range(1, len(arr)):
			pre.append(arr[i] + t)
			t = pre[-1]
		ans = [0]
		for i in range(1, len(arr)):
			if arr[i] == arr[i - 1]:
				ans.append(ans[i - 1])
			else:
				ans.append(pre[i - 1])
		d = {}
		for i in range(len(arr)):
			d[arr[i]] = ans[i]
		ans1 = []
		for i in range(len(pos)):
			ans1.append(d[pos[i][0]])
		return ans1


from typing import List
from collections import defaultdict
import bisect

class Solution:

	def smallerSum(self, n: int, arr: List[int]) -> List[int]:
		sorted_arr = sorted(arr)
		pref = [sorted_arr[0]]
		for i in range(1, n):
			pref.append(pref[i - 1] + sorted_arr[i])
		ans = [0] * n
		index_map = defaultdict(list)
		for (i, v) in enumerate(arr):
			index_map[v].append(i)
		for v in set(arr):
			ind = bisect.bisect_left(sorted_arr, v)
			if ind == 0:
				res = 0
			else:
				res = pref[ind - 1]
			for i in index_map[v]:
				ans[i] = res
		return ans


from typing import List

class Solution:

	def smallerSum(self, n: int, arr: List[int]) -> List[int]:
		dic = {}
		res = []
		prevSum = 0
		for i in arr:
			if i not in dic:
				dic[i] = 1
			else:
				dic[i] += 1
		dicArr = sorted(dic.items())
		lis = {}
		for i in dicArr:
			k = i[0]
			lis[k] = prevSum
			prevSum = prevSum + i[0] * i[1]
		mres = []
		for i in arr:
			mres.append(lis[i])
		return mres


from typing import List

class Solution:

	def smallerSum(self, n: int, arr: List[int]) -> List[int]:
		d = {}
		for i in arr:
			if i not in d:
				d[i] = 1
			else:
				d[i] += 1
		d1 = {}
		sum = 0
		l = sorted(set(arr))
		for i in l:
			d1[i] = sum
			sum += i * d[i]
		a = []
		for i in arr:
			a.append(d1[i])
		return a


from typing import List

class Solution:

	def smallerSum(self, n: int, a: List[int]) -> List[int]:
		c = sorted(a)
		k = {c[0]: 0}
		s = 0
		for i in range(1, n):
			s = s + c[i - 1]
			if c[i] != c[i - 1]:
				k[c[i]] = s
		for i in range(n):
			c[i] = k[a[i]]
		return c


from typing import List
from bisect import bisect_left

class Solution:

	def smallerSum(self, n: int, arr: List[int]) -> List[int]:
		res = []
		sorted_arr = sorted(arr)
		prefix_sum = [0] * n
		for i in range(1, n):
			prefix_sum[i] = prefix_sum[i - 1] + sorted_arr[i - 1]
		for i in range(n):
			idx = bisect_left(sorted_arr, arr[i])
			res.append(prefix_sum[idx])
		return res


from typing import List
from collections import defaultdict

class Solution:

	def smallerSum(self, n: int, a: List[int]) -> List[int]:
		map_ = defaultdict(lambda : -1)
		arr = a[:]
		arr.sort()
		ans = []
		sum = 0
		for ele in arr:
			if ele in (0, 1):
				map_[ele] = 0
			else:
				map_[ele] = sum if map_[ele] == -1 else map_[ele]
			sum += ele
		for element in a:
			ans.append(map_[element])
		return ans


from typing import List

class Solution:

	def smallerSum(self, n: int, arr: List[int]) -> List[int]:
		temp = arr.copy()
		temp.sort()
		d = {}
		d[temp[0]] = 0
		prefix_sum = temp[0]
		for i in range(1, n):
			if temp[i] == temp[i - 1]:
				prefix_sum += temp[i]
				i += 1
			else:
				d[temp[i]] = prefix_sum
				prefix_sum += temp[i]
		res = []
		for i in arr:
			res.append(d[i])
		return res


from typing import List

class Solution:

	def smallerSum(self, n: int, arr: List[int]) -> List[int]:
		B = arr.copy()
		B.sort()
		D = {B[0]: 0}
		x = 1
		for i in range(1, n):
			if B[i] > B[i - 1]:
				D[B[i]] = D[B[i - 1]] + x * B[i - 1]
				x = 1
			else:
				x = x + 1
		for j in range(n):
			arr[j] = D[arr[j]]
		return arr


from typing import List
import numpy as np

class Solution:

	def smallerSum(self, n: int, arr: List[int]) -> List[int]:
		ans = []
		arr_np = np.array(arr)
		sorted_arr = np.sort(arr_np)
		cumsum_arr = np.cumsum(sorted_arr)
		for i in arr_np:
			j = np.searchsorted(sorted_arr, i, side='left')
			ans.append(cumsum_arr[j - 1] if j > 0 else 0)
		return ans


from typing import List

class Solution:

	def smallerSum(self, n: int, arr: List[int]) -> List[int]:
		a = arr.copy()
		a.sort()
		d = {}
		temp = 0
		res = []
		for i in a:
			if i not in d:
				d[i] = temp
			temp += i
		for i in arr:
			res.append(d[i])
		return res


from typing import List
from bisect import bisect_right, bisect_left

class Solution:

	def smallerSum(self, n: int, arr: List[int]) -> List[int]:

		def binary_search(a, x):
			low = 0
			high = len(a)
			while low < high:
				mid = (low + high) // 2
				if a[mid] < x:
					low = mid + 1
				else:
					high = mid
			return low
		ans = []
		listCopy = []
		prefixSum = []
		for i in range(n):
			listCopy.append(arr[i])
		listCopy.sort()
		prefixSum = listCopy[:]
		for i in range(1, n):
			prefixSum[i] += prefixSum[i - 1]
		for val in arr:
			index = bisect_left(listCopy, val)
			if index != 0:
				ans.append(prefixSum[index - 1])
			else:
				ans.append(0)
		return ans


from typing import List
from bisect import bisect_left, bisect_right

class Solution:

	def smallerSum(self, n: int, arr: List[int]) -> List[int]:
		new = sorted(arr)
		cum = [0 for _ in range(n + 1)]
		for i in range(0, n):
			cum[i + 1] = cum[i] + new[i]

		def bs(new, k):
			st = 0
			end = n
			while st < end:
				mid = (st + end) // 2
				if new[mid] < k:
					st = mid + 1
				else:
					end = mid
			return st
		ans = [0 for _ in range(n)]
		for i in range(n):
			ans[i] = cum[bisect_left(new, arr[i])]
		return ans


from typing import List
import sys

class Solution:

	def smallerSum(self, n: int, arr: List[int]) -> List[int]:
		index = sorted(range(n), key=lambda i: arr[i])
		result = [0] * n
		sum_all = sum_less = 0
		xprev = arr[index[0]]
		for i in index:
			x = arr[i]
			if x > xprev:
				sum_less = sum_all
				xprev = x
			result[i] = sum_less
			sum_all += x
		return result


from typing import List

class Solution:

	def smallerSum(self, n: int, arr: List[int]) -> List[int]:
		sort_idx = sorted(range(len(arr)), key=lambda i: arr[i])
		sort_idx_inv = sorted(range(len(sort_idx)), key=lambda i: sort_idx[i])
		sorted_arr = [arr[sort_idx[i]] for i in range(len(arr))]
		cumsum = [0]
		cntr = 1
		for i in range(1, len(arr)):
			if sorted_arr[i] == sorted_arr[i - 1]:
				cumsum.append(cumsum[i - 1])
				cntr += 1
			else:
				cumsum.append(cumsum[i - 1] + cntr * sorted_arr[i - 1])
				cntr = 1
		return [cumsum[i] for i in sort_idx_inv]


from typing import List

class Solution:

	def smallerSum(self, n: int, arr: List[int]) -> List[int]:
		a2 = sorted(arr)
		tmp = 0
		dic = {}
		for i in range(n):
			if a2[i] in dic:
				tmp += a2[i]
			else:
				dic[a2[i]] = tmp
				tmp += a2[i]
		sol = []
		for i in range(n):
			sol.append(dic[arr[i]])
		return sol


from typing import List

class Solution:

	def smallerSum(self, n: int, arr: List[int]) -> List[int]:
		from bisect import bisect_left, bisect_right
		initial_arr = arr[:]
		arr.sort()
		sum_accumultae = [0]
		sm = 0
		for i in range(0, len(arr)):
			sm += arr[i]
			sum_accumultae.append(sm)
		ans = []
		for elem in initial_arr:
			ans.append(sum_accumultae[bisect_left(arr, elem)])
		return ans


from typing import List

class Solution:

	def smallerSum(self, n: int, arr: List[int]) -> List[int]:
		pair = []
		for i in range(n):
			pair.append([arr[i], i])
		pair = sorted(pair, key=lambda x: x[0])
		rsum = 0
		prev_sum = rsum
		prev_num = 0
		for i in range(n):
			if i == 0:
				prev_num = pair[i][0]
				rsum += pair[i][0]
				pair[i][0] = 0
			if i > 0 and pair[i][0] == prev_num:
				rsum += pair[i][0]
				pair[i][0] = prev_sum
			elif i > 0 and pair[i][0] != prev_num:
				prev_sum = rsum
				prev_num = pair[i][0]
				rsum += pair[i][0]
				pair[i][0] = prev_sum
		pair = sorted(pair, key=lambda x: x[1])
		ans = []
		for i in range(n):
			ans.append(pair[i][0])
		return ans


from typing import List
from collections import Counter

class Solution:

	def smallerSum(self, n: int, arr: List[int]) -> List[int]:
		sarr = list(set(arr))
		sarr.sort()
		carr = Counter(arr)
		d = {}
		s = 0
		for i in sarr:
			d[i] = s
			s += carr[i] * i
		ans = []
		for i in arr:
			ans.append(d[i])
		return ans


from typing import List

class Solution:

	def find(self, low, high, key, arr):
		while low < high:
			m = (low + high) // 2
			if arr[m] < key:
				low = m + 1
			else:
				high = m
		return low

	def smallerSum(self, n: int, arr: List[int]) -> List[int]:
		res = {}
		sm = 0
		temp = arr.copy()
		arr.sort()
		prefix_sum = []
		prefix_sum.append(arr[0])
		for i in range(1, n):
			r = prefix_sum[i - 1] + arr[i]
			prefix_sum.append(r)
		ans = [1] * n
		for i in range(n):
			idx = self.find(0, n - 1, temp[i], arr)
			if idx != 0:
				ans[i] = prefix_sum[idx - 1]
			else:
				ans[i] = 0
		return ans


from typing import List

class Solution:

	def smallerSum(self, n: int, arr: List[int]) -> List[int]:
		sumMap = {}
		countSet = set()
		for i in arr:
			countSet.add(i)
			if sumMap.get(i):
				sumMap[i] += i
				continue
			sumMap[i] = i
		minSumTable = {}
		sum = 0
		countSet = list(countSet)
		countSet.sort()
		for i in countSet:
			minSumTable[i] = sum
			sum += sumMap[i]
		minSum = [minSumTable[i] for i in arr]
		return minSum


from typing import List

class Solution:

	def smallerSum(self, n: int, arr: List[int]) -> List[int]:
		(l, s, d, res) = (sorted(arr), 0, {}, [])
		for i in range(n):
			if l[i] not in d:
				d[l[i]] = s
			s += l[i]
		for i in arr:
			res.append(d[i])
		return res


from typing import List
from itertools import accumulate
import bisect

class Solution:

	def smallerSum(self, n: int, arr: List[int]) -> List[int]:
		newarr = arr[:]
		res = []
		newarr.sort()
		prefix = list(accumulate(newarr))
		for i in arr:
			index = bisect.bisect_left(newarr, i)
			if index == 0:
				res.append(0)
			else:
				res.append(prefix[index - 1])
		return res


from typing import List

class Solution:

	def smallerSum(self, n: int, arr: List[int]) -> List[int]:
		k = arr.copy()
		arr.sort()
		sum = 0
		dic = {}
		tru = []
		for i in arr:
			if i not in dic:
				dic[i] = sum
			sum += i
		for i in k:
			tru.append(dic[i])
		return tru


from typing import List

class Solution:

	def smallerSum(self, n: int, arr: List[int]) -> List[int]:
		temp = arr[:]
		arr.sort()
		ans = {}
		ans[arr[0]] = 0
		cur_sum = 0
		for i in range(1, n):
			cur_sum += arr[i - 1]
			if arr[i - 1] != arr[i]:
				ans[arr[i]] = cur_sum
		result = []
		for i in temp:
			result.append(ans[i])
		return result


from typing import List

class Solution:

	def smallerSum(self, n: int, arr: List[int]) -> List[int]:
		cp = arr.copy()
		cp.sort()
		dit = {}
		pre_sum = 0
		for elem in cp:
			if elem not in dit:
				dit[elem] = pre_sum
			pre_sum += elem
		ans = []
		for i in range(n):
			ans.append(dit[arr[i]])
		return ans


from typing import List

class Solution:

	def smallerSum(self, n: int, arr: List[int]) -> List[int]:
		copy = arr.copy()
		copy.sort()
		d = {}
		pre_sum = 0
		for ele in copy:
			if ele not in d:
				d[ele] = pre_sum
			pre_sum += ele
		ans = []
		for i in range(n):
			ans.append(d[arr[i]])
		return ans


from typing import List

class Solution:

	def smallerSum(self, n: int, arr: List[int]) -> List[int]:
		d1 = {}
		for i in arr:
			if i in d1:
				d1[i] += 1
			else:
				d1[i] = 1
		d2 = {}
		s = 0
		temp = sorted(set(arr))
		for i in temp:
			d2[i] = s
			s += i * d1[i]
		ae = []
		for i in arr:
			ae.append(d2[i])
		return ae


from typing import List

class Solution:

	def smallerSum(self, n: int, arr: List[int]) -> List[int]:
		temp = arr[:]
		arr.sort()
		d = {}
		(i, pref) = (0, 0)
		while i < n:
			c = arr[i]
			t = 0
			while i < n and arr[i] == c:
				t += 1
				i += 1
			d[c] = pref
			pref += c * t
		ans = []
		for i in temp:
			ans.append(d[i])
		return ans


from typing import List

class Solution:

	def smallerSum(self, n: int, arr: List[int]) -> List[int]:
		k = sorted(arr)
		total = 0
		dic = {k[0]: 0}
		for i in range(1, n):
			total += k[i - 1]
			if k[i] not in dic:
				dic[k[i]] = total
		ans = []
		for elm in arr:
			ans.append(dic[elm])
		return ans