Geek is playing a video game that contains N monsters having varying power denoted by power[i]. Geek will play total Q rounds and for each round, the power of Geek is Q[i]. He can kill all monsters having power <= Q[i].
All the monsters which were dead in the previous round will be reborn, such that for each round there will be N monsters.
Since Geek wants to win each round, he wants to count the number of monsters he can kill in each round and total sum of their powers. Can you help him?
Example 1:
Input:
N = 7
powers[] = {1, 2, 3, 4, 5, 6, 7}
Q[] = {3, 10, 2}
Output: 
{{3, 6}, {7, 28}, {2, 3}}
Explanation:
1. For round 1, Geek has power 3, hence, it can kill
the monsters with power 1, 2 and 3. Hence, count is 3 and
total sum = 1 + 2 + 3 = 6.
2. For round 2, Geek has power 10, hence, it can kill
all the monsters. Hence, count is 7 and
total sum = 1 + 2 + ...+ 7 = 28.
3. For round 3, Geek has power 2, hence, it can kill
the first two monsters. Hence, count is 2 and
total sum = 1 + 2 = 3.
Your Task:  
You don't need to read input or print anything. Your task is to complete the function win() which takes an array of size N and another array of size Q and return list of pairs as output.
Expected Time Complexity: O(N*logN)
Expected Auxiliary Space: O(N)
 
Constraints:
1 <= N <= 10^{4}
1 <= power[i] <= 10^{2}
1<= Q <=10^{4}
1 <= Q[i[ <= 10^{2}

Source: geeksforgeeks | Difficulty: MEDIUM

Starter code: from typing import List





from typing import List





class Solution:

    def win(self, n : int, power : List[int], q : int, Q : List[int]) -> List[List[int]]:

        # code here

        



Solutions:
from typing import List
from typing import List

class Solution:

	def win(self, n: int, power: List[int], q: int, Q: List[int]) -> List[List[int]]:

		def binary(arr, ele):
			(lo, hi) = (0, len(arr) - 1)
			ans = -1
			while lo <= hi:
				mid = (lo + hi) // 2
				if arr[mid] <= ele:
					ans = mid
					lo = mid + 1
				else:
					hi = mid - 1
			return ans
		power = sorted(power)
		ans = power[:]
		for i in range(1, n):
			ans[i] += ans[i - 1]
		a = []
		for i in range(q):
			ele = Q[i]
			idx = binary(power, ele)
			if idx == -1:
				a.append((0, 0))
				continue
			a.append((idx + 1, ans[idx]))
		return a


from typing import List

class Solution:

	def binarySearch(self, power, n, x):
		(l, r) = (0, n - 1)
		while l <= r:
			mid = (l + r) // 2
			if power[mid] == x:
				return mid
			elif power[mid] > x:
				r = mid - 1
			else:
				l = mid + 1
		return l

	def win(self, n: int, power: List[int], q: int, Q: List[int]) -> List[List[int]]:
		power.sort()
		n = len(power)
		sm = [0]
		for i in power:
			sm.append(sm[-1] + i)
		ans = []
		for i in Q:
			index = self.binarySearch(power, n, i)
			while index < n and power[index] == i:
				index += 1
			if index > 0 and index < n and (power[index] == i):
				ans.append([index + 1, sm[index + 1]])
			else:
				ans.append([index, sm[index]])
		return ans


from typing import List
from typing import List

class Solution:

	def win(self, n: int, power: List[int], q: int, Q: List[int]) -> List[List[int]]:
		max_power = max(power)
		count_table = [0] * (max_power + 1)
		sum_table = [0] * (max_power + 1)
		for (i, _power) in enumerate(power):
			count_table[_power] += 1
			sum_table[_power] += _power
			for j in range(_power + 1, max_power + 1, 1):
				count_table[j] += 1
				sum_table[j] += _power
		return_list = []
		for (_, _max_power) in enumerate(Q):
			if _max_power > max_power:
				_max_power = max_power
			return_list.append([count_table[_max_power], sum_table[_max_power]])
		return return_list


from math import inf

class Solution:

	def win(self, n, power, q, Q):
		dict_Q = {x: 1 for x in Q}
		power.sort()
		ma = power[-1]
		i = -1
		currSum = 0
		dPower = {}
		dKill = {}
		power.append(inf)
		for x in range(1, ma + 1):
			while x >= power[i + 1]:
				i += 1
				currSum += power[i]
			if dict_Q.get(x) or x == ma:
				dPower[x] = currSum
				dKill[x] = i + 1
		ans = []
		for x in Q:
			if x > ma:
				ans.append([dKill[ma], dPower[ma]])
			else:
				ans.append([dKill[x], dPower[x]])
		return ans


from typing import List

class Solution:

	def binarysearch(self, n, arr, val):
		(l, r, pos) = (0, n - 1, -1)
		while l <= r:
			mid = l + (r - l) // 2
			if arr[mid] <= val:
				(pos, l) = (mid, mid + 1)
			elif arr[mid] > val:
				r = mid - 1
		return pos

	def win(self, n: int, power: List[int], q: int, Q: List[int]) -> List[List[int]]:
		power.sort()
		res = [[0, 0] for i in range(q)]
		for i in range(q):
			if Q[i] < power[0]:
				continue
			pos = self.binarysearch(n, power, Q[i])
			(res[i][0], res[i][1]) = (pos + 1, sum(power[:pos + 1]))
		return res


from typing import List
from typing import List

class Solution:

	def binary_search(self, arr, val):
		low = 0
		high = len(arr) - 1
		ceil = -1
		while low <= high:
			mid = (low + high) // 2
			if arr[mid] == val:
				low = mid + 1
			elif arr[mid] < val:
				low = mid + 1
			else:
				ceil = mid
				high = mid - 1
		return ceil

	def win(self, n: int, power: List[int], q: int, Q: List[int]) -> List[List[int]]:
		power = sorted(power)
		ans = []
		for i in range(len(Q)):
			if Q[i] >= power[0]:
				p_idx = self.binary_search(power, Q[i])
				if p_idx == -1:
					ans.append([len(power), sum(power)])
				else:
					ans.append([p_idx, sum(power[:p_idx])])
			else:
				ans.append([0, 0])
		return ans


from typing import List

class Solution:

	@staticmethod
	def findLowerBound(power, value, start, end, cur_geek_power_lower_bound):
		if start > end:
			return
		mid = end + (start - end) // 2
		if power[mid] > value:
			return Solution.findLowerBound(power, value, start, mid - 1, cur_geek_power_lower_bound)
		if power[mid] <= value:
			cur_geek_power_lower_bound[0] = mid
			return Solution.findLowerBound(power, value, mid + 1, end, cur_geek_power_lower_bound)

	def win(self, n: int, power: List[int], q: int, Q: List[int]) -> List[List[int]]:
		power.sort()
		prefixSum = [0] * n
		for index in range(n):
			if index == 0:
				prefixSum[0] = power[0]
			else:
				prefixSum[index] = prefixSum[index - 1] + power[index]
		outputList = list()
		for geekPower in Q:
			cur_geek_power_lower_bound = [-1]
			Solution.findLowerBound(power, geekPower, 0, n - 1, cur_geek_power_lower_bound)
			count = cur_geek_power_lower_bound[0] - 0 + 1
			totalSum = prefixSum[cur_geek_power_lower_bound[0]]
			outputList.append((count, totalSum))
		return outputList


from typing import List
from typing import List

class Solution:

	def win(self, n: int, power: List[int], q: int, Q: List[int]) -> List[List[int]]:
		ans = []
		power.sort()
		prefix_sum = [0]
		for i in range(n):
			prefix_sum.append(prefix_sum[-1] + power[i])
		from bisect import bisect_right
		for x in Q:
			i = bisect_right(power, x)
			ans.append([i, prefix_sum[i]])
		return ans


from typing import List
from bisect import bisect_right

class Solution:

	def win(self, n: int, power: List[int], q: int, Q: List[int]) -> List[List[int]]:
		power.sort()
		dp = [0 for i in range(n)]
		sum1 = 0
		for i in range(n):
			sum1 += power[i]
			dp[i] = sum1
		ans = []
		for i in range(q):
			j = bisect_right(power, Q[i], 0, n)
			ans.append([j, dp[j - 1]])
		return ans