Given two unsorted arrays arr1[] and arr2[]. They may contain duplicates. For each element in arr1[] count elements less than or equal to it in array arr2[].
Example 1:
Input:
m = 6, n = 6
arr1[] = {1,2,3,4,7,9}
arr2[] = {0,1,2,1,1,4}
Output: 4 5 5 6 6 6
Explanation: Number of elements less than
or equal to 1, 2, 3, 4, 7, and 9 in the
second array are respectively 4,5,5,6,6,6
Example 2:
Input:
m = 5, n = 7
arr1[] = {4,8,7,5,1}
arr2[] = {4,48,3,0,1,1,5}
Output: 5 6 6 6 3
Explanation: Number of elements less than
or equal to 4, 8, 7, 5, and 1 in the
second array are respectively 5,6,6,6,3
Your Task :
Complete the function countEleLessThanOrEqual() that takes two array arr1[], arr2[],  m, and n as input and returns an array containing the required results(the count of elements less than or equal to it in arr2 for each element in arr1 where i_{th} output represents the count for i_{th} element in arr1.)
Expected Time Complexity: O((m + n) * log n).
Expected Auxiliary Space: O(m).
Constraints:
1<=m,n<=10^5
0<=arr1[i],arr2[j]<=10^5

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Sorting

Data structures

Complete search

Starter code: #User function Template for python3



class Solution:

    def countEleLessThanOrEqual(self,arr1,n1,arr2,n2):

        #returns the required output

    

Solutions:
class Solution:

	def countEleLessThanOrEqual(self, array1, n1, array2, n2):
		n1_size = max(array1)
		n2_size = max(array2)
		holder = [0 for i in range(max(n1_size, n2_size) + 1)]
		for i in array2:
			holder[i] += 1
		count = 0
		for i in range(len(holder)):
			count += holder[i]
			holder[i] = count
		count = 0
		for i in range(n1):
			array1[i] = holder[array1[i]]
		return array1


from bisect import bisect_right

class Solution:

	def countEleLessThanOrEqual(self, arr1, n1, arr2, n2):
		arr2.sort()
		ans = []
		for i in arr1:
			idx = bisect_right(arr2, i)
			ans.append(idx)
		return ans


class Solution:

	def find_last(self, nums, x):
		low = 0
		high = len(nums) - 1
		while low <= high:
			mid = low + (high - low) // 2
			if nums[mid] <= x:
				low = mid + 1
			elif nums[mid] > x:
				high = mid - 1
		return high

	def countEleLessThanOrEqual(self, arr1, n1, arr2, n2):
		arr2.sort()
		ans = []
		for i in range(n1):
			x = arr1[i]
			idx = self.find_last(arr2, x)
			ans.append(idx + 1)
		return ans


class Solution:

	def countEleLessThanOrEqual(self, arr1, n1, arr2, n2):

		def bs(val, arr):
			i = 0
			j = len(arr) - 1
			while i <= j:
				m = (i + j) // 2
				if arr[m] <= val:
					i = m + 1
				else:
					j = m - 1
			return i
		lst = []
		arr2.sort()
		for i in arr1:
			lst.append(bs(i, arr2))
		return lst


class Solution:

	def countEleLessThanOrEqual(self, arr1, n1, arr2, n2):
		(s, sm_till, mx) = (0, [], max(max(arr1), max(arr2)))
		freq = [0] * (mx + 1)
		for elem in arr2:
			freq[elem] += 1
		for elem in freq:
			s += elem
			sm_till.append(s)
		return [sm_till[elem] for elem in arr1]


class Solution:

	def countEleLessThanOrEqual(self, arr1, n1, arr2, n2):
		max1 = max(arr2)
		temp = [0 for i in range(max1 + 1)]
		for i in arr2:
			temp[i] += 1
		for i in range(1, max1 + 1):
			temp[i] += temp[i - 1]
		return [temp[i] if i < max1 + 1 else temp[-1] for i in arr1]


class Solution:

	def countEleLessThanOrEqual(self, arr1, m, arr2, n):
		arr2.sort()
		result = []
		for i in range(m):
			(left, right) = (0, n - 1)
			while left <= right:
				mid = left + (right - left) // 2
				if arr2[mid] > arr1[i]:
					right = mid - 1
				else:
					left = mid + 1
			result.append(left)
		return result


class Solution:

	def countEleLessThanOrEqual(self, arr1, n1, arr2, n2):
		arr2.sort()
		ans = []

		def lastIndex(num):
			(start, end) = (0, len(arr2) - 1)
			while start <= end:
				mid = start + (end - start) // 2
				if arr2[mid] <= num:
					start = mid + 1
				else:
					end = mid - 1
			return start
		for num in arr1:
			ind = lastIndex(num)
			ans.append(ind)
		return ans


from collections import Counter

class Solution:

	def countEleLessThanOrEqual(self, arr1, n1, arr2, n2):
		max1 = max(arr2)
		temp = [0 for i in range(max1 + 1)]
		for i in arr2:
			temp[i] += 1
		for i in range(1, max1 + 1):
			temp[i] += temp[i - 1]
		return [temp[i] if i < max1 + 1 else temp[-1] for i in arr1]


class Solution:

	def binary(self, k, arr2, end):
		start = 0
		ans = -1
		while start <= end:
			mid = start + (end - start) // 2
			if arr2[mid] <= k:
				ans = mid
				start = mid + 1
			else:
				end = mid - 1
		return ans + 1

	def countEleLessThanOrEqual(self, arr1, n1, arr2, n2):
		arr2.sort()
		for i in range(n1):
			arr1[i] = self.binary(arr1[i], arr2, n2 - 1)
		return arr1


class Solution:

	def countEleLessThanOrEqual(self, arr1, n1, arr2, n2):
		arr2.sort()

		def search(x):
			low = 0
			high = len(arr2)
			while low < high:
				mid = low + (high - low) // 2
				if arr2[mid] < x:
					low = mid + 1
				else:
					high = mid
			return low
		ans = [-1] * n1
		for i in range(n1):
			k = search(arr1[i] + 1) - 1
			ans[i] = k + 1
		return ans


from bisect import bisect_right

class Solution:

	def countEleLessThanOrEqual(self, arr1, n1, arr2, n2):
		arr2.sort()
		r = []
		for i in arr1:
			ind = bisect_right(arr2, i)
			r.append(ind)
		return r


import bisect

class Solution:

	def countEleLessThanOrEqual(self, arr1, n1, arr2, n2):
		arr2.sort()
		res = []
		for num in arr1:
			res.append(bisect.bisect_right(arr2, num))
		return res


class Solution:

	def countEleLessThanOrEqual(self, arr1, n1, arr2, n2):
		r = [n2] * n1
		arr2.sort()
		for i in range(n1):
			l = 0
			h = n2 - 1
			while l <= h:
				m = (l + h) // 2
				if arr2[m] > arr1[i]:
					r[i] = m
					h = m - 1
				elif arr2[m] <= arr1[i]:
					l = m + 1
		return r


class Solution:

	def binarysearch(self, arr2, n2, x):
		ans = -1
		low = 0
		high = n2 - 1
		while low <= high:
			mid = (low + high) // 2
			if arr2[mid] <= x:
				ans = mid
				low = mid + 1
			elif arr2[mid] > x:
				high = mid - 1
		return ans + 1

	def countEleLessThanOrEqual(self, arr1, n1, arr2, n2):
		arr2.sort()
		lst = []
		for i in range(n1):
			ans = self.binarysearch(arr2, n2, arr1[i])
			lst.append(ans)
		return lst


class Solution:

	def countEleLessThanOrEqual(self, arr1, n1, arr2, n2):

		def count(arr, x):
			low = 0
			high = len(arr) - 1
			while low <= high:
				mid = (low + high) // 2
				if x >= arr[mid]:
					low = mid + 1
				elif x < arr[mid]:
					high = mid - 1
				else:
					return low
			return low
		arr2.sort()
		li = []
		for i in range(n1):
			li.append(count(arr2, arr1[i]))
		return li


class Solution:

	def countEleLessThanOrEqual(self, arr1, n1, arr2, n2):

		def searchLast(arr, target):
			l = 0
			r = len(arr) - 1
			while l <= r:
				mid = (l + r) // 2
				if arr[mid] == target:
					l = mid + 1
				elif arr[mid] > target:
					r = mid - 1
				else:
					l = mid + 1
			return r + 1
		ans = []
		arr2.sort()
		for i in arr1:
			ans.append(searchLast(arr2, i))
		return ans


def mgc(arr, x):
	(st, en) = (0, len(arr) - 1)
	ans = len(arr)
	while st <= en:
		mid = (st + en) // 2
		if arr[mid] > x:
			ans = mid
			en = mid - 1
		else:
			st = mid + 1
	return ans

class Solution:

	def countEleLessThanOrEqual(self, arr1, n1, arr2, n2):

		def ind(x, arr):
			low = 0
			high = len(arr) - 1
			while low <= high:
				mid = (low + high) // 2
				if arr2[mid] <= x:
					low = mid + 1
				else:
					high = mid - 1
			return low
		li = []
		arr2.sort()
		for i in range(n1):
			s = ind(arr1[i], arr2)
			li.append(s)
		return li


def mgc(arr, x):
	(st, en) = (0, len(arr) - 1)
	ans = len(arr)
	while st <= en:
		mid = (st + en) // 2
		if arr[mid] > x:
			ans = mid
			en = mid - 1
		else:
			st = mid + 1
	if x == len(arr) and arr[0] > x:
		return 0
	return ans

class Solution:

	def countEleLessThanOrEqual(self, arr1, n1, arr2, n2):
		arr2.sort()
		ans = []
		for i in arr1:
			ind = mgc(arr2, i)
			ans.append(ind)
		return ans


class Solution:

	def binsearch(self, arr, k, n):
		s = 0
		e = n - 1
		res = -1
		while s <= e:
			m = (s + e) // 2
			if arr[m] == k:
				res = m
				s = m + 1
			if arr[m] < k:
				res = m
				s = m + 1
			if arr[m] > k:
				e = m - 1
		if res != -1:
			return res + 1
		else:
			return 0

	def countEleLessThanOrEqual(self, arr1, n1, arr2, n2):
		ans = []
		arr2.sort()
		for i in range(n1):
			ans.append(self.binsearch(arr2, arr1[i], n2))
		return ans


class Solution:

	def countEleLessThanOrEqual(self, arr1, n1, arr2, n2):
		arr2.sort()
		for i in range(n1):
			key = arr1[i]
			(l, h) = (0, n2 - 1)
			index = -1
			while l <= h:
				mid = (l + h) // 2
				if arr2[mid] <= arr1[i]:
					index = mid
					l = mid + 1
				elif arr2[mid] > arr1[i]:
					h = mid - 1
			if index == -1:
				arr1[i] = 0
			else:
				arr1[i] = index + 1
		return arr1


class Solution:

	def countEleLessThanOrEqual(self, arr1, n1, arr2, n2):
		ans = []
		arr2.sort()
		for i in range(n1):
			count = 0
			s = 0
			e = n2 - 1
			mid = 0
			while s <= e:
				mid = (s + e) // 2
				if arr2[mid] <= arr1[i]:
					s = mid + 1
				else:
					e = mid - 1
			ans.append(s)
		return ans


class Solution:

	def countEleLessThanOrEqual(self, arr1, n1, arr2, n2):
		lst = []
		arr2.sort()
		for i in range(n1):
			cnt = 0
			low = 0
			mid = 0
			high = n2 - 1
			while low <= high:
				mid = (low + high) // 2
				if arr2[mid] <= arr1[i]:
					low = mid + 1
				else:
					high = mid - 1
			lst.append(low)
		return lst


class Solution:

	def countEleLessThanOrEqual(self, arr1, n1, arr2, n2):
		import bisect
		l = []
		arr2.sort()
		for i in range(n1):
			count = bisect.bisect_right(arr2, arr1[i])
			l.append(count)
		return l


class Solution:

	def countEleLessThanOrEqual(self, arr1, n1, arr2, n2):
		arr2.sort()

		def check(arr2, n2, i):
			low = 0
			high = n2 - 1
			while low <= high:
				mid = (low + high) // 2
				if arr2[mid] >= i:
					high = mid - 1
				else:
					low = mid + 1
			return low

		def check2(arr2, n2, i):
			low = 0
			high = n2 - 1
			while low <= high:
				mid = (low + high) // 2
				if arr2[mid] <= i:
					low = mid + 1
				else:
					high = mid - 1
			return low
		x = []
		for i in arr1:
			x.append(check2(arr2, n2, i))
		return x


class Solution:

	def countEleLessThanOrEqual(self, arr1, n1, arr2, n2):
		arr2.sort()
		ar = []
		for i in arr1:
			l = 0
			u = n2 - 1
			ind = n2
			while l <= u:
				m = (l + u) // 2
				if arr2[m] > i:
					u = m - 1
				else:
					l = m + 1
			ar.append(l)
		return ar


class Solution:

	def countEleLessThanOrEqual(self, arr1, n1, arr2, n2):
		ma = max(arr2)
		l = [0] * (ma + 1)
		for i in arr2:
			l[i] += 1
		for i in range(1, ma + 1):
			l[i] += l[i - 1]
		return [l[i] if i < ma + 1 else l[-1] for i in arr1]


class Solution:

	def countEleLessThanOrEqual(self, arr1, n1, arr2, n2):
		arr2.sort()
		mini = arr2[0]
		maxi = arr2[n2 - 1]
		for i in range(n1):
			if arr1[i] < mini:
				arr1[i] = 0
			elif arr1[i] > maxi:
				arr1[i] = n2
			else:
				start = 0
				end = n2 - 1
				ans = 0
				while start <= end:
					mid = start + (end - start) // 2
					if arr2[mid] == arr1[i]:
						ans = mid
						start = mid + 1
					elif arr2[mid] < arr1[i]:
						start = mid + 1
					elif arr2[mid] > arr1[i]:
						end = mid - 1
					else:
						arr1[i] = start
				if ans == 0:
					arr1[i] = start
				else:
					arr1[i] = ans + 1
		return arr1


from collections import OrderedDict

class Solution:

	def countEleLessThanOrEqual(self, arr1, n1, arr2, n2):
		arr3 = arr1.copy()
		arr1.sort()
		arr2.sort()
		dic = {}
		res = []
		(i, j) = (0, 0)
		count = 0
		while i < n1:
			while j < n2 and arr2[j] <= arr1[i]:
				count += 1
				j += 1
			dic[arr1[i]] = count
			i += 1
		for i in range(n1):
			res.append(dic[arr3[i]])
		return res


class Solution:

	def countEleLessThanOrEqual(self, arr1, n1, arr2, n2):
		ans = [0] * n1
		arr2.sort()
		for i in range(n1):
			temp = 0
			low = 0
			high = n2 - 1
			while low <= high:
				mid = (low + high) // 2
				if arr2[mid] <= arr1[i]:
					temp = max(temp, mid + 1)
					low = mid + 1
				else:
					high = mid - 1
			ans[i] = temp
		return ans


class Solution:

	def Just_smaller(self, arr2, n, val):
		start = 0
		end = n - 1
		mx = -1
		while start <= end:
			middle = (start + end) // 2
			if arr2[middle] <= val:
				mx = middle
				start = middle + 1
			else:
				end = middle - 1
		return mx

	def countEleLessThanOrEqual(self, arr1, n1, arr2, n2):
		ans = []
		arr2.sort()
		for i in range(n1):
			index = self.Just_smaller(arr2, n2, arr1[i])
			ans.append(index + 1)
		return ans


import bisect

class Solution:

	def countEleLessThanOrEqual(self, arr1, n1, arr2, n2):
		arr2.sort()
		ans = []
		for i in range(n1):
			t = bisect.bisect(arr2, arr1[i])
			ans.append(t)
		return ans


class Solution:

	def countEleLessThanOrEqual(self, arr1, n1, arr2, n2):
		arr2.sort()
		counts = []
		for i in range(n1):
			count = self.binarySearch(arr2, n2, arr1[i])
			counts.append(count)
		return counts

	def binarySearch(self, arr, n, x):
		low = 0
		high = n - 1
		while low <= high:
			mid = (low + high) // 2
			if arr[mid] <= x:
				low = mid + 1
			else:
				high = mid - 1
		return low


class Solution:

	def countEleLessThanOrEqual(self, arr1, n1, arr2, n2):
		arr2.sort()
		result = []
		for x in arr1:
			index = self.binarySearch(arr2, n2, x)
			result.append(index)
		return result

	def binarySearch(self, arr, n, x):
		(left, right) = (0, n - 1)
		while left <= right:
			mid = left + (right - left) // 2
			if arr[mid] <= x:
				left = mid + 1
			else:
				right = mid - 1
		return left


class Solution:

	def countEleLessThanOrEqual(self, arr1, n1, arr2, n2):
		arr = arr1.copy()
		arr1.sort()
		arr2.sort()
		dic = {}
		ans = []
		prev = 0
		i = 0
		for elm in arr1:
			count = 0
			while i < n2:
				if arr2[i] <= elm:
					count += 1
					i += 1
				else:
					prev = prev + count
					dic[elm] = prev
					break
			else:
				dic[elm] = n2
		return [dic[elm] for elm in arr]


class Solution:

	def countEleLessThanOrEqual(self, arr1, n1, arr2, n2):
		copy = arr1[:]
		arr1.sort()
		arr2.sort()
		prev_count = 0
		res = {}
		j = 0
		for i in arr1:
			curr_count = 0
			while j < len(arr2):
				if arr2[j] <= i:
					curr_count += 1
					j += 1
				else:
					break
			res[i] = curr_count + prev_count
			prev_count = curr_count + prev_count
		ans = []
		for i in copy:
			ans.append(res[i])
		return ans


def search(arr, x):
	s = 0
	e = len(arr) - 1
	while s <= e:
		m = (s + e) // 2
		if arr[m] <= x:
			s = m + 1
		else:
			e = m - 1
	return e

class Solution:

	def countEleLessThanOrEqual(self, arr1, n1, arr2, n2):
		arr2.sort()
		arr3 = []
		for i in range(n1):
			x = search(arr2, arr1[i])
			arr3.append(x + 1)
		return arr3


class Solution:

	def countEleLessThanOrEqual(self, arr1, n1, arr2, n2):
		res = [0] * n1
		arr2.sort()
		for i in range(n1):
			s = 0
			e = n2 - 1
			if n2 == 1:
				if arr1[i] >= arr2[0]:
					res[i] = 1
				else:
					res[i] = 0
			if arr1[i] >= arr2[n2 - 1]:
				res[i] = n2
			else:
				while s <= e:
					m = (s + e) // 2
					if arr2[m] > arr1[i] and arr2[m - 1] <= arr1[i]:
						res[i] = m
						break
					elif arr2[m] <= arr1[i]:
						s = m + 1
					else:
						e = m - 1
		return res


class Solution:

	def countEleLessThanOrEqual(self, arr1, n1, arr2, n2):
		arr2.sort()
		ans = []
		for i in range(n1):
			l = 0
			h = n2 - 1
			while l <= h:
				mid = (l + h) // 2
				if arr2[mid] < arr1[i] + 1:
					l = mid + 1
				else:
					h = mid - 1
			ans.append(l)
		return ans


class Solution:

	def upper_bound(self, arr, n, x):
		l = 0
		h = n - 1
		while l < h:
			m = l + (h - l) // 2
			if arr[m] <= x:
				l = m + 1
			else:
				h = m
		if arr[h] > x:
			return h
		if arr[l] > x:
			return l
		return -1

	def countEleLessThanOrEqual(self, arr1, n1, arr2, n2):
		ans = []
		arr2.sort()
		for i in range(n1):
			val = self.upper_bound(arr2, n2, arr1[i])
			ans.append(val if val != -1 else n2)
		return ans


class Solution:

	def countEleLessThanOrEqual(self, arr1, n1, arr2, n2):
		arr = arr1.copy()
		arr1.sort()
		arr2.sort()
		d = {}
		c = j = 0
		for i in arr1:
			while j < n2:
				if arr2[j] > i:
					break
				c += 1
				j += 1
			d[i] = c
		arr3 = []
		for i in arr:
			arr3.append(d[i])
		return arr3


from bisect import bisect_right

class Solution:

	def countEleLessThanOrEqual(self, arr1, n1, arr2, n2):
		arr2.sort()
		lis = []
		for i in arr1:
			k = bisect_right(arr2, i)
			lis.append(k)
		return lis


from bisect import bisect_right as v

class Solution:

	def countEleLessThanOrEqual(self, arr1, n1, arr2, n2):
		arr2.sort()
		l = []
		for i in arr1:
			res = v(arr2, i)
			l.append(res)
		return l


class Solution:

	def countEleLessThanOrEqual(self, arr1, n1, arr2, n2):

		def search(arr, i):
			first = 0
			last = len(arr) - 1
			while first <= last:
				mid = (first + last) // 2
				if arr[mid] == i:
					first = mid + 1
				elif arr[mid] > i:
					last = mid - 1
				else:
					first = mid + 1
			return last + 1
		res = []
		arr2.sort()
		for i in arr1:
			res.append(search(arr2, i))
		return res


class Solution:

	def countEleLessThanOrEqual(self, arr1, n1, arr2, n2):
		arr2.sort()
		ans = []
		for i in arr1:
			l = 0
			r = n2 - 1
			while l <= r:
				m = (l + r) // 2
				if i >= arr2[m]:
					l = m + 1
				else:
					r = m - 1
			ans.append(l)
		return ans


class Solution:

	def countEleLessThanOrEqual(self, arr1, n1, arr2, n2):
		k = []
		for i in arr1:
			k.append(i)
		arr1.sort()
		arr2.sort()
		d = {}
		j = 0
		v = []
		for i in range(n1):
			while j < n2 and arr2[j] <= arr1[i]:
				j += 1
			d[arr1[i]] = j
		for i in range(n1):
			v.append(d[k[i]])
		return v


class Solution:

	def countEleLessThanOrEqual(self, a1, n1, a2, n2):
		a2.sort()
		ans = []
		for i in range(n1):
			low = 0
			high = n2 - 1
			mid = (high + low) // 2
			if a1[i] >= a2[high]:
				ans.append(n2)
			elif a1[i] < a2[low]:
				ans.append(0)
			else:
				while mid > 0 and mid < n2 - 1:
					if a1[i] >= a2[mid] and a1[i] < a2[mid + 1]:
						ans.append(mid + 1)
						break
					elif a1[i] < a2[mid]:
						high = mid
						mid = (high + low) // 2
					else:
						low = mid
						mid = (high + low) // 2
				if mid == 0 and a1[i] >= a2[0]:
					ans.append(1)
		return ans


def bin_search(arr, n, x):
	l = 0
	h = n - 1
	while l <= h:
		mid = int((l + h) // 2)
		if arr[mid] <= x:
			l = mid + 1
		else:
			h = mid - 1
	return h

class Solution:

	def countEleLessThanOrEqual(self, arr1, n1, arr2, n2):
		l = []
		arr2.sort()
		for i in range(n1):
			index = bin_search(arr2, n2, arr1[i])
			l.append(index + 1)
		return l


class Solution:

	def countEleLessThanOrEqual(self, arr1, n1, arr2, n2):
		arr2.sort()

		def bin_sea(arr, tar):
			high = len(arr) - 1
			low = 0
			ans = 0
			while low < high:
				mid = (high + low) // 2
				if arr[mid] == tar:
					return mid
				elif arr[mid] < tar:
					low = mid + 1
					ans = low
				else:
					high = mid - 1
			return ans if arr[ans] >= tar else ans + 1
		op = []
		for i in range(n1):
			ans = bin_sea(arr2, arr1[i])
			while ans < n2 and arr2[ans] == arr1[i]:
				ans += 1
			op.append(ans)
		return op


class Solution:

	def countEleLessThanOrEqual(self, arr1, n1, arr2, n2):
		arr2.sort()

		def binarysearch(arr, target):
			start = 0
			end = len(arr) - 1
			ans = 0
			while start < end:
				mid = (start + end) // 2
				if arr[mid] == target:
					return mid
				elif arr[mid] < target:
					start = mid + 1
					ans = mid + 1
				else:
					end = mid - 1
			return ans if arr[ans] >= target else ans + 1
		opt = []
		for i in range(len(arr1)):
			ans = binarysearch(arr2, arr1[i])
			while ans < n2 and arr2[ans] == arr1[i]:
				ans += 1
			opt.append(ans)
		return opt


class Solution:

	def solve(self, nums, target):
		l = 0
		r = len(nums) - 1
		san = len(nums)
		while l <= r:
			mid = (l + r) // 2
			if nums[mid] <= target:
				l = mid + 1
			else:
				r = mid - 1
				san = mid
		else:
			return san

	def countEleLessThanOrEqual(self, arr1, n1, arr2, n2):
		ans = []
		arr2.sort()
		for i in arr1:
			ans.append(self.solve(arr2, i))
		return ans


class Solution:

	def countEleLessThanOrEqual(self, arr1, n1, arr2, n2):

		def bin(arr, n, x):
			s = 0
			s1 = n - 1
			while s <= s1:
				mid = s + (s1 - s) // 2
				if arr[mid] <= x:
					s = mid + 1
				else:
					s1 = mid - 1
			return s1
		arr2.sort()
		ans = []
		for i in range(n1):
			pos = bin(arr2, n2, arr1[i])
			ans.append(pos + 1)
		return ans


class Solution:

	def countEleLessThanOrEqual(self, arr1, n1, arr2, n2):
		m = []
		l = [0] * (max(max(arr1), max(arr2)) + 1)
		for ele in arr2:
			l[ele] += 1
		p = []
		p.append(l[0])
		for i in range(1, len(l)):
			p.append(p[i - 1] + l[i])
		for ele in arr1:
			m.append(p[ele])
		return m


class Solution:

	def countEleLessThanOrEqual(self, arr1, n1, arr2, n2):
		res = []
		arr2.sort()

		def binary(target, n2):
			low = 0
			high = n2 - 1
			ans = 0
			while low <= high:
				mid = low + (high - low) // 2
				if arr2[mid] > target:
					ans = mid
					high = mid - 1
				else:
					if mid + 1 >= n2:
						ans = mid + 1
					low = mid + 1
			return ans
		for i in range(n1):
			index = binary(arr1[i], n2)
			res.append(index)
		return res


class Solution:

	def countEleLessThanOrEqual(self, arr1, n1, arr2, n2):
		l = []
		m = max(arr2)
		temp = [0 for i in range(m + 1)]
		for i in arr2:
			temp[i] += 1
		for i in range(1, m + 1):
			temp[i] += temp[i - 1]
		for i in arr1:
			if i < m + 1:
				l.append(temp[i])
			else:
				l.append(temp[-1])
		return l


import bisect as bis

class Solution:

	def countEleLessThanOrEqual(self, arr1, n1, arr2, n2):
		s = []
		arr2.sort()
		for i in arr1:
			s.append(bis.bisect(arr2, i))


import bisect as bt

class Solution:

	def countEleLessThanOrEqual(self, arr1, n1, arr2, n2):
		arr2.sort()
		res = []
		for e in arr1:
			res.append(bt.bisect_right(arr2, e))
		return res


from math import inf

class Solution:

	def countEleLessThanOrEqual(self, arr1, n1, arr2, n2):
		arr2.sort()
		arr2.append(inf)
		p = 0
		d = {}
		for x in range(max(arr1) + 1):
			while arr2[p] <= x:
				p += 1
			d[x] = p
		return [d[x] for x in arr1]