<p>You are given two <strong>0-indexed</strong> arrays <code>nums</code> and <code>cost</code> consisting each of <code>n</code> <strong>positive</strong> integers.</p>

<p>You can do the following operation <strong>any</strong> number of times:</p>

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

<p>The cost of doing one operation on the <code>i<sup>th</sup></code> element is <code>cost[i]</code>.</p>

<p>Return <em>the <strong>minimum</strong> total cost such that all the elements of the array </em><code>nums</code><em> become <strong>equal</strong></em>.</p>

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

<pre>
<strong>Input:</strong> nums = [1,3,5,2], cost = [2,3,1,14]
<strong>Output:</strong> 8
<strong>Explanation:</strong> We can make all the elements equal to 2 in the following way:
- Increase the 0<sup>th</sup> element one time. The cost is 2.
- Decrease the 1<sup><span style="font-size: 10.8333px;">st</span></sup> element one time. The cost is 3.
- Decrease the 2<sup>nd</sup> element three times. The cost is 1 + 1 + 1 = 3.
The total cost is 2 + 3 + 3 = 8.
It can be shown that we cannot make the array equal with a smaller cost.
</pre>

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

<pre>
<strong>Input:</strong> nums = [2,2,2,2,2], cost = [4,2,8,1,3]
<strong>Output:</strong> 0
<strong>Explanation:</strong> All the elements are already equal, so no operations are needed.
</pre>

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

<ul>
	<li><code>n == nums.length == cost.length</code></li>
	<li><code>1 &lt;= n &lt;= 10<sup>5</sup></code></li>
	<li><code>1 &lt;= nums[i], cost[i] &lt;= 10<sup>6</sup></code></li>
	<li>Test cases are generated in a way that the output doesn&#39;t exceed&nbsp;2<sup>53</sup>-1</li>
</ul>

class Solution {
public:
    long long minCost(vector<int>& nums, vector<int>& cost) {
        /*
        Observations:
        Even if the values are the same, then the cost may be different
        The answer lies in the values itself
        
        Let us sort both the arrays as per the index
        
        v1, v2, v3, ..x.., v4, v5
        Prefix: (x - v1)c1 + (x - v2)c2 + (x - v3)c3
              : x(c1 + c2 + c3) - (v1c1 + v2c2 + v3c3)
              
        Suffix: (v4 - x)c4 + (v5 - x)c5
              : (v4c4 + v5c5) - x(c4 + c5)
        */
        int n = nums.size();
        vector<array<long long, 2>> numsIdx;
        
        for(int it = 0; it < n; it++)
        {
            numsIdx.push_back({nums[it], it});
        }
        
        sort(begin(numsIdx), end(numsIdx));
        vector<long long> nums1;
        for(auto &x:numsIdx) nums1.emplace_back(x[0]);
        
        vector<long long> costPref(n, 0), constTerm(n, 0);
        
        costPref[0] = cost[numsIdx[0][1]];
        constTerm[0] = numsIdx[0][0] * cost[numsIdx[0][1]];
        
        for(int it = 1; it < n; it++)
        {
            costPref[it] = costPref[it - 1] + cost[numsIdx[it][1]];
            constTerm[it] = constTerm[it - 1] + numsIdx[it][0] * cost[numsIdx[it][1]];
        }
        long long ans = (long long)1e18;
        for(long long x = 1; x <= (int)1e6; x++)
        {
            auto it = lower_bound(nums1.begin(),nums1.end(),x);
            auto index=it-nums1.begin();
            long long costHere = 0;
            if(index)
                costHere+=costPref[index-1]*x-constTerm[index-1];
            if(index<(int)nums.size())
            {
                long long temp=-x*(costPref.back()-(index ? costPref[index-1] : 0))+constTerm.back()-(index ? constTerm[index-1] : 0);
                costHere+=temp;
            }
            ans=min(ans,costHere);
        }
        return ans;
    }
};
54900