<p>You are given an array <code>nums</code> consisting of positive integers.</p>

<p>You are also given an integer array <code>queries</code> of size <code>m</code>. For the <code>i<sup>th</sup></code> query, you want to make all of the elements of <code>nums</code> equal to<code> queries[i]</code>. You can perform the following operation on the array <strong>any</strong> number of times:</p>

<ul>
	<li><strong>Increase</strong> or <strong>decrease</strong> an element of the array by <code>1</code>.</li>
</ul>

<p>Return <em>an array </em><code>answer</code><em> of size </em><code>m</code><em> where </em><code>answer[i]</code><em> is the <strong>minimum</strong> number of operations to make all elements of </em><code>nums</code><em> equal to </em><code>queries[i]</code>.</p>

<p><strong>Note</strong> that after each query the array is reset to its original state.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> nums = [3,1,6,8], queries = [1,5]
<strong>Output:</strong> [14,10]
<strong>Explanation:</strong> For the first query we can do the following operations:
- Decrease nums[0] 2 times, so that nums = [1,1,6,8].
- Decrease nums[2] 5 times, so that nums = [1,1,1,8].
- Decrease nums[3] 7 times, so that nums = [1,1,1,1].
So the total number of operations for the first query is 2 + 5 + 7 = 14.
For the second query we can do the following operations:
- Increase nums[0] 2 times, so that nums = [5,1,6,8].
- Increase nums[1] 4 times, so that nums = [5,5,6,8].
- Decrease nums[2] 1 time, so that nums = [5,5,5,8].
- Decrease nums[3] 3 times, so that nums = [5,5,5,5].
So the total number of operations for the second query is 2 + 4 + 1 + 3 = 10.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> nums = [2,9,6,3], queries = [10]
<strong>Output:</strong> [20]
<strong>Explanation:</strong> We can increase each value in the array to 10. The total number of operations will be 8 + 1 + 4 + 7 = 20.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>n == nums.length</code></li>
	<li><code>m == queries.length</code></li>
	<li><code>1 &lt;= n, m &lt;= 10<sup>5</sup></code></li>
	<li><code>1 &lt;= nums[i], queries[i] &lt;= 10<sup>9</sup></code></li>
</ul>

from collections import defaultdict
class Solution:
    def minOperations(self, nums: List[int], queries: List[int]) -> List[int]:
        # res = []
        # mapQuery = {}
        # countNums = defaultdict(int)
        # # for query in queries:
        # #     countQueries[query] += 1
        # for num in nums:
        #     countNums[num] += 1
        # for query in queries:
        #     currRes = 0
        #     # print(keyQuery, valQuery)
        #     if query in mapQuery:
        #         currRes = mapQuery[query]
        #     else:
        #         for keyNum, valNum in countNums.items():
        #             # print("=====",keyNum, valNum)
        #             currRes += abs(keyNum - query) * valNum
        #             # print(currRes)
        #         mapQuery[query] = currRes
        #     res.append(currRes)
        # return res
        nums.sort()
        prefix_sum = [nums[0]]
        ans = []
        for i in range(1, len(nums)):
            prefix_sum.append(prefix_sum[-1] + nums[i])
        
        for target in queries:
            l = 0
            r = len(nums) - 1
            pos = -2 # -2 for not found case
            #left bin search             
            while l <= r:
                mid = (l + r) // 2
                if nums[mid] > target:
                    r = mid - 1
                elif nums[mid] < target:
                    l = mid + 1
                else:
                    pos = mid
                    r = mid - 1     

            if pos == -2:
                pos = min(l, r)
            # pos == -1 leftmost case
            if pos == -1:
                ans.append(prefix_sum[-1] - (len(nums))*target)
            else:
                ans.append((pos+1)*target - prefix_sum[pos] + prefix_sum[-1] - prefix_sum[pos] - (len(nums) -1 - pos)*target)
            
        return ans
        
43600