Given two arrays X and Y of positive integers, find the number of pairs such that x^{y} > y^{x} (raised to power of) where x is an element from X and y is an element from Y.
Example 1:
Input: 
M = 3, X[] = [2 1 6] 
N = 2, Y[] = [1 5]
Output: 3
Explanation: 
The pairs which follow x^{y} > y^{x} are 
as such: 2^{1} > 1^{2},  2^{5} > 5^{2} and 6^{1} > 1^{6 .}
Example 2:
Input: 
M = 4, X[] = [2 3 4 5]
N = 3, Y[] = [1 2 3]
Output: 5
Explanation: 
The pairs for the given input are 
2^{1 }> 1^{2} , 3^{1} > 1^{3 }, 3^{2} > 2^{3} , 4^{1} > 1^{4} , 
5^{1} > 1^{5 }.
Your Task:
This is a function problem. You only need to complete the function countPairs() that takes X, Y, M, N as parameters and returns the total number of pairs.
Expected Time Complexity: O((N + M)log(N)).
Expected Auxiliary Space: O(1).
Constraints:
1 ≤ M, N ≤ 10^{5}
1 ≤ X[i], Y[i] ≤ 10^{3}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Sorting

Starter code: #User function Template for python3



class Solution:

    

     #Function to count number of pairs such that x^y is greater than y^x.     

    def countPairs(self,a,b,M,N):

        #code here

Solutions:
class Solution:

	def countPairs(self, a, b, M, N):
		from bisect import bisect as bi
		a.sort()
		b.sort()
		ans = 0
		for X in a:
			if X == 1:
				continue
			elif X == 2:
				ans += bi(b, 1) + N - bi(b, 4)
			elif X == 3:
				ans += bi(b, 2) + N - bi(b, 3)
			else:
				ans += bi(b, 1) + N - bi(b, X)
		return ans


import bisect

class Solution:

	def count(self, x, b, n, noOfY):
		if x == 0:
			return 0
		if x == 1:
			return noOfY[0]
		idx = bisect.bisect_right(b, x)
		ans = n - idx
		ans += noOfY[0] + noOfY[1]
		if x == 2:
			ans -= noOfY[3] + noOfY[4]
		if x == 3:
			ans += noOfY[2]
		return ans

	def countPairs(self, a, b, m, n):
		noOfY = [0] * 5
		for i in range(n):
			if b[i] < 5:
				noOfY[b[i]] += 1
		b.sort()
		totalPairs = 0
		for x in a:
			totalPairs += self.count(x, b, n, noOfY)
		return totalPairs


import bisect

class Solution:

	def elements_greater_than_current(self, find, b, N):
		s = 0
		e = N - 1
		while s <= e:
			m = s + (e - s) // 2
			if b[m] == find:
				if m == N - 1:
					return 0
				if b[m + 1] != find:
					return N - m - 1
				s = m + 1
			elif b[m] > find:
				e = m - 1
			else:
				s = m + 1
		return N - s

	def countPairs(self, a, b, M, N):
		b.sort()
		one_count = 0
		two_count = 0
		three_count = 0
		four_count = 0
		for i in range(N):
			if b[i] == 1:
				one_count += 1
			elif b[i] == 2:
				two_count += 1
			elif b[i] == 3:
				three_count += 1
			elif b[i] == 4:
				four_count += 1
			else:
				break
		c = 0
		for i in range(M):
			if a[i] != 1:
				idx = bisect.bisect_right(b, a[i])
				greater_count = N - idx
				greater_count += one_count
				if a[i] == 2:
					greater_count -= three_count + four_count
				elif a[i] == 3:
					greater_count += two_count
				c += greater_count
		return c


import bisect

class Solution:

	def count(self, x_i, y, n, no_of_y):
		if x_i == 0:
			return 0
		if x_i == 1:
			return no_of_y[0]
		idx = bisect.bisect_right(y, x_i)
		pair_count = n - idx
		pair_count += no_of_y[0] + no_of_y[1]
		if x_i == 2:
			pair_count -= no_of_y[3] + no_of_y[4]
		if x_i == 3:
			pair_count += no_of_y[2]
		return pair_count

	def countPairs(self, x, y, m, n):
		pair_count = 0
		y.sort()
		no_of_y = [0] * 5
		for i in range(n):
			if y[i] < 5:
				no_of_y[y[i]] += 1
			else:
				break
		for i in range(m):
			pair_count += self.count(x[i], y, n, no_of_y)
		return pair_count


from bisect import bisect_right
from bisect import bisect_left
import bisect

class Solution:

	def counts(self, b):
		zeros = b.count(0)
		ones = b.count(1)

	def countPairs(self, a, b, M, N):
		zeros = b.count(0)
		ones = b.count(1)
		two = b.count(2)
		three = b.count(3)
		four = b.count(4)
		x = a
		y = b
		y.sort()
		ans = 0
		for i in range(len(x)):
			if x[i] == 0:
				continue
			elif x[i] == 1:
				ans += zeros
			elif x[i] == 2:
				index = bisect_right(y, x[i])
				ans += N - index
				ans -= three
				ans -= four
				ans += ones + zeros
			elif x[i] == 3:
				index = bisect_right(y, x[i])
				ans += N - index
				ans += ones + zeros
				ans += two
			else:
				index = bisect_right(y, x[i])
				ans += N - index
				ans += ones + zeros
		return ans


class Solution:

	def count(self, x, Y, n, NoOfY):
		if x == 0:
			return 0
		if x == 1:
			return NoOfY[0]
		idx = bisect.bisect_right(Y, x)
		ans = n - idx
		ans += NoOfY[0] + NoOfY[1]
		if x == 2:
			ans -= NoOfY[3] + NoOfY[4]
		if x == 3:
			ans += NoOfY[2]
		return ans

	def countPairs(self, a, b, M, N):
		NoOfY = [0] * 5
		for i in range(N):
			if b[i] < 5:
				NoOfY[b[i]] += 1
		b.sort()
		total_pairs = 0
		for x in a:
			total_pairs += self.count(x, b, N, NoOfY)
		return total_pairs


import bisect

class Solution:

	def countPairs(self, a, b, M, N):
		NoOfb = [0, 0, 0, 0, 0]
		for i in range(N):
			if b[i] < 5:
				NoOfb[b[i]] += 1
		b.sort()
		total_pairs = 0
		for i in range(M):
			total_pairs += self.count(a[i], b, N, NoOfb)
		return total_pairs

	def count(self, x, b, N, NoOfb):
		if not x:
			return x
		if x == 1:
			return NoOfb[0]
		index = bisect.bisect_right(b, x)
		ans = 0
		if index < N and b[index] > x:
			ans += N - index
		ans += NoOfb[0] + NoOfb[1]
		if x == 2:
			ans -= NoOfb[3] + NoOfb[4]
		if x == 3:
			ans += NoOfb[2]
		return ans


def count(x, Y, n, NoOfY):
	if x == 0:
		return 0
	if x == 1:
		return NoOfY[0]
	idx = bisect.bisect_right(Y, x)
	ans = n - idx
	ans += NoOfY[0] + NoOfY[1]
	if x == 2:
		ans -= NoOfY[3] + NoOfY[4]
	if x == 3:
		ans += NoOfY[2]
	return ans

class Solution:

	def countPairs(self, X, Y, m, n):
		NoOfY = [0] * 5
		for i in range(n):
			if Y[i] < 5:
				NoOfY[Y[i]] += 1
		Y.sort()
		total_pairs = 0
		for x in X:
			total_pairs += count(x, Y, n, NoOfY)
		return total_pairs


import bisect

class Solution:

	def countPairs(self, X, Y, m, n):
		ans = 0
		a.sort()
		b.sort()
		zero = b.count(0)
		one = b.count(1)
		four = b.count(4)
		three = b.count(3)
		two = b.count(2)
		for i in a:
			if i == 0:
				continue
			elif i == 1:
				ans = ans + zero
			if i > 1:
				idx = bisect.bisect_right(b, i)
				countx = N - idx
				ans = ans + countx
				ans = ans + zero + one
			if i == 2:
				ans = ans - three - four
			elif i == 3:
				ans = ans + two
		return ans


class Solution:

	def countPairs(self, a, b, M, N):
		ans = 0
		a.sort()
		b.sort()
		zero = b.count(0)
		one = b.count(1)
		four = b.count(4)
		three = b.count(3)
		two = b.count(2)
		for i in a:
			if i == 0:
				continue
			elif i == 1:
				ans = ans + zero
			if i > 1:
				idx = bisect.bisect_right(b, i)
				countx = N - idx
				ans = ans + countx
				ans = ans + zero + one
			if i == 2:
				ans = ans - three - four
			elif i == 3:
				ans = ans + two
		return ans


import bisect

class Solution:

	def countPairs(self, a, b, M, N):
		total_count = 0
		freq = [0] * 5
		for i in range(N):
			if b[i] < 5:
				freq[b[i]] += 1
		b.sort()
		for i in range(M):
			total_count += Solution.count_numbers(a[i], b, N, freq)
		return total_count

	def count_numbers(x, b, N, freq):
		count = 0
		if x == 0:
			return 0
		if x == 1:
			return freq[0]
		idx = bisect.bisect_right(b, x)
		count = N - idx
		count = count + freq[0] + freq[1]
		if x == 2:
			count -= freq[3] + freq[4]
		if x == 3:
			count += freq[2]
		return count


import bisect as bs

class Solution:

	def countPairs(self, a, b, M, N):
		X = a.copy()
		Y = b.copy()
		X.sort()
		Y.sort()
		count = 0
		(y1, y0, y2, y3, y4) = (0, 0, 0, 0, 0)
		for i in range(N):
			if Y[i] == 0:
				y0 += 1
			elif Y[i] == 1:
				y1 += 1
			elif Y[i] == 2:
				y2 += 1
			elif Y[i] == 3:
				y3 += 1
			elif Y[i] == 4:
				y4 += 1
		for i in range(M):
			if X[i] == 0:
				continue
			elif X[i] == 1:
				count += y0
			elif X[i] == 2:
				k = bs.bisect_right(Y, 2)
				count += N - k
				count -= y3
				count -= y4
				count += y1 + y0
			else:
				j = bs.bisect_right(Y, X[i])
				count += N - j
				count += y1 + y0
				if X[i] == 3:
					count += y2
		return count


import bisect
import operator as op

class Solution:

	def count(self, i, b, no0, no1, no2, no3, no4):
		count_ = 0
		if i == 0:
			return 0
		if i == 1:
			return no0
		idx = bisect.bisect_right(b, i)
		count_ = len(b) - idx
		count_ += no0 + no1
		if i == 2:
			count_ -= no3 + no4
		if i == 3:
			count_ += no2
		return count_

	def countPairs(self, a, b, M, N):
		total_pairs = 0
		b.sort()
		no0 = op.countOf(b, 0)
		no1 = op.countOf(b, 1)
		no2 = op.countOf(b, 2)
		no3 = op.countOf(b, 3)
		no4 = op.countOf(b, 4)
		for i in a:
			total_pairs += self.count(i, b, no0, no1, no2, no3, no4)
		return total_pairs


class Solution:

	def countPairs(self, x, y, M, N):
		(zero, one, two, three, four) = (0, 0, 0, 0, 0)
		for item in y:
			if item == 0:
				zero += 1
			elif item == 1:
				one += 1
			elif item == 2:
				two += 1
			elif item == 3:
				three += 1
			elif item == 4:
				four += 1
		y.sort()
		ans = 0
		for item in x:
			if item == 1:
				ans += zero
			elif item == 2:
				ind = self.binSearch(y, 2)
				ans += len(y) - ind
				ans += zero
				ans += one
				ans -= three
				ans -= four
			elif item == 3:
				ind = self.binSearch(y, 3)
				ans += len(y) - ind
				ans += zero
				ans += one
				ans += two
			elif item > 3:
				ind = self.binSearch(y, item)
				ans += len(y) - ind
				ans += zero
				ans += one
		return ans

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


import math
import sys

class Solution:

	def countPairs(self, a, b, M, N):
		count = int(0)
		nums_1 = []
		nums_2 = []
		for i in range(0, len(a), 1):
			if math.log(a[i]) == 0:
				nums_1.append(sys.maxsize)
			else:
				nums_1.append(a[i] / math.log(a[i]))
		for i in range(0, len(b), 1):
			if math.log(b[i]) == 0:
				nums_2.append(sys.maxsize)
			else:
				nums_2.append(b[i] / math.log(b[i]))
		nums_1.sort()
		nums_2.sort()
		p = int(0)
		q = int(0)
		while p < len(nums_1) and q < len(nums_2):
			if nums_1[p] < nums_2[q]:
				count += len(nums_2) - q
				p += 1
			else:
				q += 1
		return count


class Solution:

	def countPairs(self, a, b, M, N):
		for i in range(M):
			a[i] = a[i] ** (1 / a[i])
		a.sort(reverse=True)
		for i in range(N):
			b[i] = b[i] ** (1 / b[i])
		b.sort(reverse=True)
		po = 0
		count = 0
		for i in range(M):
			while po < N:
				if a[i] > b[po]:
					count += N - po
					break
				else:
					po += 1
		return count


class Solution:

	def getIndex(self, b, n, ele):
		low = 0
		high = n - 1
		ans = -1
		while low <= high:
			mid = (low + high) // 2
			if b[mid] > ele:
				ans = mid
				high = mid - 1
			else:
				low = mid + 1
		return ans

	def countPairs(self, a, b, M, N):
		ans = zero = one = two = three = four = 0
		a = sorted(a)
		b = sorted(b)
		for i in b:
			if i == 0:
				zero += 1
			if i == 1:
				one += 1
			if i == 2:
				two += 1
			if i == 3:
				three += 1
			if i == 4:
				four += 1
		ans = 0
		for i in range(len(a)):
			if a[i] == 0:
				continue
			elif a[i] == 1:
				ans += zero
			elif a[i] == 2:
				index = self.getIndex(b, N, 2)
				if index != -1:
					ans += N - index
				ans -= three
				ans -= four
				ans += one + zero
			else:
				index = self.getIndex(b, N, a[i])
				if index != -1:
					ans += N - index
				ans += one + zero
				if a[i] == 3:
					ans += two
		return ans


class Solution:

	def countPairs(self, X, Y, m, n):
		for i in range(m):
			X[i] **= 1 / X[i]
		for i in range(n):
			Y[i] **= 1 / Y[i]
		X.sort()
		Y.sort()
		i = j = 0
		ans = 0
		while i < m:
			if j == n:
				ans += n
			else:
				while j < n and X[i] > Y[j]:
					j += 1
				ans += j
			i += 1
		return ans


class Solution:

	def countPairs(self, X, Y, M, N):
		zeroes = 0
		ones = 0
		twos = 0
		threes = 0
		fours = 0
		answer = 0
		X.sort()
		Y.sort()
		for i in range(len(Y)):
			if Y[i] == 0:
				zeroes += 1
			if Y[i] == 1:
				ones += 1
			if Y[i] == 3:
				threes += 1
			if Y[i] == 4:
				fours += 1
			if Y[i] == 2:
				twos = twos + 1
		for i in range(len(X)):
			if X[i] == 0:
				continue
			elif X[i] == 1:
				answer = answer + zeroes
			elif X[i] == 2:
				idx = bisect.bisect_right(Y, 2)
				count = len(Y) - idx
				answer = answer + count
				answer = answer - (threes + fours)
				answer = answer + (zeroes + ones)
			elif X[i] == 3:
				idx = bisect.bisect_right(Y, 3)
				count = len(Y) - idx
				answer = answer + count
				answer = answer + ones + twos
			else:
				idx = bisect.bisect_right(Y, X[i])
				count2 = len(Y) - idx
				answer = answer + count2
				answer = answer + ones
				answer = answer + zeroes
		return answer


class Solution:

	def search(self, y, n, k):
		low = 0
		high = n - 1
		ans = -1
		while low <= high:
			middle = (low + high) // 2
			if y[middle] > k:
				ans = middle
				high = middle - 1
			else:
				low = middle + 1
		return ans

	def countPairs(self, a, b, M, N):
		b.sort()
		zeros = 0
		ones = 0
		twos = 0
		threes = 0
		fours = 0
		for i in b:
			if i == 0:
				zeros += 1
			elif i == 1:
				ones += 1
			elif i == 2:
				twos += 1
			elif i == 3:
				threes += 1
			elif i == 4:
				fours += 1
		ans = 0
		for i in a:
			if i == 0:
				continue
			elif i == 1:
				ans += zeros
			elif i == 2:
				id = self.search(b, N, i)
				if id != -1:
					ans += N - id
				ans -= threes + fours
				ans += zeros + ones
			else:
				id = self.search(b, N, i)
				if id != -1:
					ans += N - id
				ans += zeros + ones
				if i == 3:
					ans += twos
		return ans


class Solution:

	def countPairs(self, a, b, M, N):
		b.sort()
		numOnes = 0
		numTwos = 0
		for x in b:
			if x == 1:
				numOnes += 1
			elif x == 2:
				numTwos += 1
			else:
				break
		res = 0
		for x in a:
			if x > 1:
				res += numOnes
				if x == 2:
					x = 4
				elif x == 3:
					res += numTwos
				idx = self.binarySearch(b, x)
				if idx >= 0:
					res += N - idx
		return res

	def binarySearch(self, arr, x):
		n = len(arr)
		lo = 0
		hi = n - 1
		res = -1
		while lo <= hi:
			mid = (lo + hi) // 2
			if arr[mid] > x:
				res = mid
				hi = mid - 1
			else:
				lo = mid + 1
		return res


import bisect

class Solution:

	def countPairs(self, a, b, M, N):
		a.sort()
		b.sort()
		zeros = 0
		ones = 0
		twos = 0
		three = 0
		four = 0
		ans = 0
		for i in range(N):
			if b[i] == 0:
				zeros += 1
			elif b[i] == 1:
				ones += 1
			elif b[i] == 2:
				twos += 1
			elif b[i] == 3:
				three += 1
			elif b[i] == 4:
				four += 1
		for j in range(M):
			if a[j] == 0:
				continue
			elif a[j] == 1:
				ans += zeros
			elif a[j] == 2:
				count = N - bisect.bisect_right(b, a[j])
				ans += count
				ans += zeros + ones
				ans -= three
				ans -= four
			else:
				count = N - bisect.bisect_right(b, a[j])
				ans += count
				ans += zeros + ones
				if a[j] == 3:
					ans += twos
		return ans


class Solution:

	def countPairs(self, a, b, M, N):

		def binary_search(arr, s, e, num):
			last_gt = -1
			while s <= e:
				mid = (s + e) // 2
				if arr[mid] > num:
					e = mid - 1
					last_gt = mid
				else:
					s = mid + 1
			return last_gt
		b.sort()
		zc = 0
		oc = 0
		tc = 0
		thc = 0
		fc = 0
		for num in b:
			if num == 0:
				zc += 1
			elif num == 1:
				oc += 1
			elif num == 2:
				tc += 1
			elif num == 3:
				thc += 1
			elif num == 4:
				fc += 1
		count = 0
		for num in a:
			if num == 0:
				continue
			elif num == 1:
				count += zc
			elif num == 2:
				count += oc + zc
				index = binary_search(b, 0, N - 1, num)
				count += N - index if index != -1 else 0
				count -= thc + fc
			else:
				count += oc + zc
				index = binary_search(b, 0, N - 1, num)
				count += N - index if index != -1 else 0
				if num == 3:
					count += tc
		return count


import math

class Solution:

	def countPairs(self, a, b, M, N):

		def trans(x):
			return math.log2(x) / x
		b.sort(key=trans)
		a.sort(key=trans)
		k = 0
		j = 0
		for i in a:
			while j < N and trans(i) > trans(b[j]):
				j += 1
			k += j
		return k


class Solution:

	def countPairs(self, a, b, M, N):

		def getind(arr, n, key):
			(l, r) = (0, n - 1)
			ans = -1
			while l <= r:
				mid = (l + r) // 2
				if arr[mid] > key:
					r = mid - 1
					ans = mid
				else:
					l = mid + 1
			return ans
		(z, o, to, t, f) = (0, 0, 0, 0, 0)
		ans = 0
		a.sort()
		b.sort()
		for ele in b:
			if ele == 0:
				z += 1
			elif ele == 1:
				o += 1
			elif ele == 2:
				to += 1
			elif ele == 3:
				t += 1
			elif ele == 4:
				f += 1
		for ele in a:
			if ele == 0:
				pass
			elif ele == 1:
				ans += z
			elif ele == 2:
				ind = getind(b, N, 2)
				if ind != -1:
					ans += N - ind
				ans -= t + f
				ans += o + z
			else:
				ind = getind(b, N, ele)
				if ind != -1:
					ans += N - ind
				ans += z + o
				if ele == 3:
					ans += to
		return ans


class Solution:

	def getIndex(self, b, N, k):
		low = 0
		high = N - 1
		ans = -1
		while low <= high:
			mid = (low + high) // 2
			if b[mid] > k:
				ans = mid
				high = mid - 1
			else:
				low = mid + 1
		return ans

	def countPairs(self, a, b, M, N):
		a.sort()
		b.sort()
		count = 0
		(zeroes, ones, two, three, four) = (0, 0, 0, 0, 0)
		for i in b:
			if i == 0:
				zeroes = zeroes + 1
			elif i == 1:
				ones = ones + 1
			elif i == 2:
				two = two + 1
			elif i == 3:
				three = three + 1
			elif i == 4:
				four = four + 1
		for i in a:
			if i == 0:
				continue
			elif i == 1:
				count = count + zeroes
			elif i == 2:
				index = Solution.getIndex(self, b, N, 2)
				if index != -1:
					count = count + N - index
					count = count - three - four
				count = count + zeroes + ones
			elif i == 3:
				index = Solution.getIndex(self, b, N, i)
				if index != -1:
					count = count + N - index
				count = count + two
				count = count + zeroes + ones
			else:
				index = Solution.getIndex(self, b, N, i)
				if index != -1:
					count = count + N - index
				count = count + zeroes + ones
		return count


class Solution:

	def countPairs(self, a, b, M, N):
		sm = 0
		b.sort(reverse=1)
		from collections import Counter
		c = Counter(b)
		from bisect import bisect_left as bl
		for x in a:
			if x > 3:
				sm += c[1]
				sm += self.countGreater(b, x, N)
			elif x == 3:
				sm += c[1] + c[2]
				sm += self.countGreater(b, x, N)
			elif x == 2:
				sm += c[1]
				sm += self.countGreater(b, 4, N)
		return sm

	def countGreater(self, b, x, N):
		lo = 0
		hi = N - 1
		ans = 0
		while lo <= hi:
			mi = (lo + hi) // 2
			if b[mi] > x:
				ans = mi + 1
				lo = mi + 1
			else:
				hi = mi - 1
		return ans


import bisect

class Solution:

	def countPairs(self, a, b, M, N):
		b.sort()
		count = 0
		numb = [0] * 5
		for i in range(N):
			if b[i] < 5:
				numb[b[i]] += 1
		for i in range(M):
			if a[i] == 0:
				continue
			elif a[i] == 1:
				count += numb[0]
			elif a[i] == 2:
				count -= numb[3] + numb[4]
				bi = bisect.bisect_right(b, a[i])
				count += N - bi
				count += numb[0] + numb[1]
			elif a[i] == 3:
				count += numb[2]
				bi = bisect.bisect_right(b, a[i])
				count += N - bi
				count += numb[0] + numb[1]
			else:
				bi = bisect.bisect_right(b, a[i])
				count += N - bi
				count += numb[0] + numb[1]
		return count


import math

class Solution:

	def transform(self, x):
		return math.log(x, 2) / x

	def countPairs(self, a, b, M, N):
		a.sort(key=lambda x: self.transform(x))
		b.sort(key=lambda x: self.transform(x))
		ans = 0
		k = 0
		for element in a:
			while k < len(b) and self.transform(element) > self.transform(b[k]):
				k += 1
			ans += k
		return ans


def binarySearch(nums, target):
	(l, r) = (0, len(nums))
	while l < r:
		m = (l + r) // 2
		if nums[m] < target:
			l = m + 1
		else:
			r = m
	return l

class Solution:

	def countPairs(self, a, b, M, N):
		a.sort()
		ans = 0
		i = 0
		while a[i] == 1:
			i += 1
		ones = i
		while a[i] == 2:
			i += 1
		twos = i - ones
		while a[i] == 3:
			i += 1
		threes = i - ones - twos
		for y in b:
			if y > 4:
				ind = binarySearch(a, y)
				ans += ind - ones
			elif y == 1:
				ans += M - ones
			elif y == 2 or y == 4:
				ans += threes
		return ans


class Solution:

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

	def countPairs(self, a, b, n, m):
		a.sort()
		b.sort()
		s = 0
		d = {}
		for i in b:
			d[i] = d.get(i, 0) + 1
		(z, o, t, h, f) = (d.get(0, 0), d.get(1, 0), d.get(2, 0), d.get(3, 0), d.get(4, 0))
		for i in a:
			if i == 0 or i == 1:
				continue
			if i == 2:
				x = self.binary(b, m, 2)
				s += x
				s -= h + f
				s += z + o
			elif i == 3:
				x = self.binary(b, m, 3)
				s += x
				s += z + o + t
			else:
				x = self.binary(b, m, i)
				s += x
				s += z + o
		return s


import bisect

class Solution:

	def upperBound(self, arr, val):
		length = len(arr)
		idx = bisect.bisect_right(arr, val)
		if idx == length:
			return -1
		return idx

	def upperBound1(self, arr, val):
		max = len(arr) - 1
		min = 0
		if val >= arr[max]:
			return -1
		while min <= max:
			index = min + int((max - min + 1) / 2)
			if val == arr[index]:
				while index + 1 <= len(arr) - 1 and arr[index + 1] == arr[index]:
					index += 1
				if index + 1 > len(arr) - 1:
					return -1
				return index
			elif val > arr[index]:
				min = index + 1
			else:
				max = index - 1
		if val > arr[index]:
			return index + 1
		else:
			return index

	def countPairs(self, a, b, M, N):
		bLength = len(b)
		b.sort()
		count = 0
		i = 0
		while i < bLength:
			if b[i] == 0:
				i += 1
			else:
				break
		if i == 0:
			zeroes = 0
		else:
			zeroes = i - 1
		ones = 0
		while i < bLength:
			if b[i] == 1:
				i += 1
				ones += 1
			else:
				break
		twos = 0
		while i < bLength:
			if b[i] == 2:
				i += 1
				twos += 1
			else:
				break
		threes = 0
		while i < bLength:
			if b[i] == 3:
				i += 1
				threes += 1
			else:
				break
		fours = 0
		while i < bLength:
			if b[i] == 4:
				i += 1
				fours += 1
			else:
				break
		for x in a:
			if x == 0:
				continue
			if x == 1:
				count += zeroes
				continue
			if x == 2:
				if self.upperBound(b, 4) == -1:
					count += zeroes + ones
				else:
					count += zeroes + ones + bLength - self.upperBound(b, 4)
				continue
			if x == 3:
				threeUB = self.upperBound(b, 3)
				if threeUB == -1:
					count += zeroes + ones + twos
				else:
					count += zeroes + ones + twos + bLength - threeUB
				continue
			xUB = self.upperBound(b, x)
			if xUB == -1:
				count += zeroes + ones
			else:
				count += zeroes + ones + bLength - xUB
		return count


import bisect

class Solution:

	def count(self, NofB, N, b, element):
		if element == 0:
			return 0
		if element == 1:
			return NofB[0]
		t = bisect.bisect_right(b, element)
		ans = N - t
		ans += NofB[0] + NofB[1]
		if element == 2:
			ans -= NofB[3] + NofB[4]
		if element == 3:
			ans += NofB[2]
		return ans

	def countPairs(self, a, b, M, N):
		b.sort()
		NofB = [0] * 5
		for i in range(N):
			if b[i] < 5:
				NofB[b[i]] += 1
		total_pairs = 0
		for element in a:
			total_pairs += self.count(NofB, N, b, element)
		return total_pairs


import bisect

class Solution:

	def countPairs(self, a, b, M, N):
		Ans = 0
		b = sorted(b)
		C0 = b.count(0)
		C1 = b.count(1)
		C2 = b.count(2)
		for i in range(M):
			if a[i] == 0:
				pass
			elif a[i] == 1:
				Ans += C0
			elif a[i] == 2:
				Ans += C0 + C1
				it = bisect.bisect_right(b, a[i])
				if it < N:
					Ans = Ans + N - it
				Ans = Ans - b.count(3) - b.count(4)
			elif a[i] == 3:
				Ans += C0 + C1 + C2
				it = bisect.bisect_right(b, a[i])
				if it < N:
					Ans = Ans + N - it
			else:
				Ans += C0 + C1
				it = bisect.bisect_right(b, a[i])
				if it < N:
					Ans = Ans + N - it
		return Ans


import bisect

class Solution:

	def do(self, x, Y, N, count):
		if x == 0:
			return 0
		if x == 1:
			return count[0]
		indx = bisect.bisect_right(Y, x)
		ans = N - indx
		ans += count[0] + count[1]
		if x == 2:
			ans -= count[3] + count[4]
		if x == 3:
			ans += count[2]
		return ans

	def countPairs(self, a, b, M, N):
		count = [0] * 5
		for i in b:
			if i < 5:
				count[i] += 1
		b.sort()
		res = 0
		for i in a:
			res += self.do(i, b, N, count)
		return res


class Solution:

	def sol(self, item, b, N, countb):
		from bisect import bisect_right
		if item == 1:
			return 0
		index = bisect_right(b, item)
		ans = N - index
		ans += countb[1]
		if item == 2:
			ans -= countb[3] + countb[4]
		if item == 3:
			ans += countb[2]
		return ans

	def countPairs(self, a, b, M, N):
		b.sort()
		countb = [0] * 5
		for i in range(N):
			if b[i] < 5:
				countb[b[i]] += 1
			else:
				break
		count = 0
		for i in range(M):
			count += self.sol(a[i], b, N, countb)
		return count


class Solution:

	def countPairs(self, a, b, M, N):
		x = [0] * 5
		for i in b:
			if i < 5:
				x[i] += 1
		b.sort()
		count = 0
		for i in a:
			count += self.getCount(i, b, x)
		return count

	def getCount(self, i, b, x):
		if i == 0:
			return 0
		if i == 1:
			return x[0]
		ans = x[0] + x[1]
		if i == 2:
			ans -= x[3]
			ans -= x[4]
		if i == 3:
			ans += x[2]
		s = 0
		e = len(b) - 1
		while s < e:
			mid = (s + e) // 2
			if i < b[mid]:
				e = mid - 1
			else:
				s = mid + 1
		if i < b[s]:
			ans += len(b) - s
		else:
			ans += len(b) - s - 1
		return ans


class Solution:

	def elemgttar(self, arr, n, tar):
		l = 0
		h = n - 1
		res = -1
		while l <= h:
			m = l + h >> 1
			if arr[m] > tar:
				res = m
				h = m - 1
			else:
				l = m + 1
		return res

	def countPairs(self, a, b, M, N):
		b.sort()
		exceptionarr = [0] * 5
		for i in b:
			if i in range(5):
				exceptionarr[i] = exceptionarr[i] + 1
		ans = 0
		for i in a:
			if i == 0:
				continue
			elif i == 1:
				ans = ans + exceptionarr[0]
			else:
				index_gt_x = self.elemgttar(b, N, i)
				if index_gt_x != -1:
					ans = ans + N - index_gt_x
				ans = ans + exceptionarr[0] + exceptionarr[1]
				if i == 2:
					ans = ans - exceptionarr[3] - exceptionarr[4]
				elif i == 3:
					ans = ans + exceptionarr[2]
		return ans


import bisect

class Solution:

	def countPairs(self, a, b, M, N):
		yarr = sorted(b)
		y_oneortwo = bisect.bisect_right(yarr, 2)
		y_ones = bisect.bisect_right(yarr, 1, 0, y_oneortwo)
		result = 0
		for x in a:
			if x > 3:
				dr = y_ones + N - bisect.bisect_right(yarr, x)
			elif x == 3:
				dr = y_oneortwo + N - bisect.bisect_right(yarr, 3)
			elif x == 2:
				dr = y_ones + N - bisect.bisect_right(yarr, 4)
			else:
				dr = 0
			result += dr
		return result


import bisect

class Solution:

	def countPairs(self, a, b, M, N):
		Ans = 0
		b = sorted(b)
		c0 = b.count(0)
		c1 = b.count(1)
		c2 = b.count(2)
		for i in range(M):
			if a[i] == 0:
				pass
			elif a[i] == 1:
				Ans += c0
			elif a[i] == 2:
				Ans += c0 + c1
				it = bisect.bisect_right(b, a[i])
				if it < N:
					Ans += N - it
				Ans = Ans - b.count(3) - b.count(4)
			elif a[i] == 3:
				Ans += c0 + c1 + c2
				it = bisect.bisect_right(b, a[i])
				if it < N:
					Ans += N - it
			else:
				Ans += c0 + c1
				it = bisect.bisect_right(b, a[i])
				if it < N:
					Ans += N - it
		return Ans


import bisect

def util(x, y, n, freq):
	if x == 0:
		return 0
	if x == 1:
		return freq[0]
	idx = bisect.bisect_right(y, x)
	ans = n - idx
	ans += freq[0] + freq[1]
	if x == 2:
		ans -= freq[3] + freq[4]
	if x == 3:
		ans += freq[2]
	return ans

class Solution:

	def countPairs(self, x, y, m, n):
		freq = [0] * 5
		for i in range(n):
			if y[i] < 5:
				freq[y[i]] += 1
		y.sort()
		count = 0
		for x in x:
			count += util(x, y, n, freq)
		return count


class Solution:

	def upper_bound(self, arr, x):
		low = 0
		high = len(arr) - 1
		while low <= high:
			mid = low + high >> 1
			if arr[mid] <= x:
				low = mid + 1
			else:
				high = mid - 1
		return low

	def count(self, x, Y, N, in_y):
		if x == 0:
			return 0
		if x == 1:
			return in_y[0]
		idx = self.upper_bound(Y, x)
		res = N - idx
		res += in_y[0] + in_y[1]
		if x == 2:
			res -= in_y[3] + in_y[4]
		if x == 3:
			res += in_y[2]
		return res

	def countPairs(self, X, Y, M, N):
		in_y = [0] * 5
		for i in range(N):
			if Y[i] < 5:
				in_y[Y[i]] += 1
		Y.sort()
		total_pairs = 0
		for i in range(M):
			x = X[i]
			total_pairs += self.count(x, Y, N, in_y)
		return total_pairs