<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>

"""
<Solution 1> 傳統解法 - TC非常耗時
 => TC: O(n*q), SC: O(q)

1. 遍歷nums中每一個num，計算num與query的差(取絕對值)。
2. 加總所有的差。

<Solution 2> Sort + Prefix + Binary Search [次快]
1. 將nums由小到大排序 => sorted_nums
2. 計算sorted_nums的累計總和 => prefixed_num
3. 利用binary search在sorted_nums中找出比query"小"的idx，這些元素的總和就是prefix_nums[idx]
   steps += -1 * (prefixed_num[i]-num*(元素總和))
   
   反之，利用binary search在sorted_nums中找出比query"大"的idx，這些元素的總和就是prefix_nums[idx]
   steps += 1 * (prefixed_num[i]-num*(元素總和))
4. 將結果append到output中，即為結果。

<Solution 3> Accumulate + Bisect_left [最快]
=> TC: (n+q)*log(n), SC: O(q)
1. 將nums由小到大排序 => sort
2. 計算sorted_nums的累計總和 => accumulate
3. 找尋比query"小"的idx，計算出要執行的operations => bisect_left
"""

class Solution:
    def minOperations(self, nums: List[int], queries: List[int]) -> List[int]:
        """
        Solution 3: Accumulate + Bisect_left
        """
        n = len(nums)
        nums.sort()
        prefix_sum = list(accumulate(nums, initial=0))
        
        output = []
        for q in queries:
            target_idx = bisect_left(nums, q)  # 找出比q還要小中的最大元素's idx
            left = q * target_idx - prefix_sum[target_idx]
            right = prefix_sum[n] - prefix_sum[target_idx] - q * (n - target_idx)
            output.append(left+right)
        return output

        """
        Solution 2: Sort + Prefix + Binary Search
        """
        # sort the nums
        sorted_nums = sorted(nums)

        # prefix_nums 
        prefix_nums = [0] * len(sorted_nums)
        prefix_nums[0] = sorted_nums[0]
        for i in range(1, len(sorted_nums)):
            prefix_nums[i] = prefix_nums[i-1] + sorted_nums[i]
        
        # binary search helper
        def binary_search(arr, target):
            l, r = 0, len(arr)
            while l < r:
                mid = l + (r-l)//2
                if arr[mid] < target:
                    l = mid + 1
                elif arr[mid] > target:
                    r = mid
            return l
        
        # 計算 steps
        output = []
        for query in queries:
            target_idx = binary_search(sorted_nums, query)
            steps = 0
            # sum of operations for nums < query
            if target_idx > 0:
                left_sum = query * target_idx - prefix_nums[target_idx-1]
                steps += left_sum
            # sum of operations for nums > query
            if target_idx < len(sorted_nums):
                right_sum = (prefix_nums[-1] - (prefix_nums[target_idx - 1] if target_idx > 0 else 0)) - query * (len(sorted_nums) - target_idx)
                steps += right_sum
            output.append(steps)
        return output

        """
        Solution 1: (傳統解法)
        """
        output = []

        for query in queries:
            steps = 0
            for n in nums:
                steps += abs(n-query)
            output.append(steps)
            
        return output
        
695