<p>Given an integer array <code>instructions</code>, you are asked to create a sorted array from the elements in <code>instructions</code>. You start with an empty container <code>nums</code>. For each element from <strong>left to right</strong> in <code>instructions</code>, insert it into <code>nums</code>. The <strong>cost</strong> of each insertion is the <b>minimum</b> of the following:</p>

<ul>
	<li>The number of elements currently in <code>nums</code> that are <strong>strictly less than</strong> <code>instructions[i]</code>.</li>
	<li>The number of elements currently in <code>nums</code> that are <strong>strictly greater than</strong> <code>instructions[i]</code>.</li>
</ul>

<p>For example, if inserting element <code>3</code> into <code>nums = [1,2,3,5]</code>, the <strong>cost</strong> of insertion is <code>min(2, 1)</code> (elements <code>1</code> and <code>2</code> are less than <code>3</code>, element <code>5</code> is greater than <code>3</code>) and <code>nums</code> will become <code>[1,2,3,3,5]</code>.</p>

<p>Return <em>the <strong>total cost</strong> to insert all elements from </em><code>instructions</code><em> into </em><code>nums</code>. Since the answer may be large, return it <strong>modulo</strong> <code>10<sup>9</sup> + 7</code></p>

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

<pre>
<strong>Input:</strong> instructions = [1,5,6,2]
<strong>Output:</strong> 1
<strong>Explanation:</strong> Begin with nums = [].
Insert 1 with cost min(0, 0) = 0, now nums = [1].
Insert 5 with cost min(1, 0) = 0, now nums = [1,5].
Insert 6 with cost min(2, 0) = 0, now nums = [1,5,6].
Insert 2 with cost min(1, 2) = 1, now nums = [1,2,5,6].
The total cost is 0 + 0 + 0 + 1 = 1.</pre>

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

<pre>
<strong>Input:</strong> instructions = [1,2,3,6,5,4]
<strong>Output:</strong> 3
<strong>Explanation:</strong> Begin with nums = [].
Insert 1 with cost min(0, 0) = 0, now nums = [1].
Insert 2 with cost min(1, 0) = 0, now nums = [1,2].
Insert 3 with cost min(2, 0) = 0, now nums = [1,2,3].
Insert 6 with cost min(3, 0) = 0, now nums = [1,2,3,6].
Insert 5 with cost min(3, 1) = 1, now nums = [1,2,3,5,6].
Insert 4 with cost min(3, 2) = 2, now nums = [1,2,3,4,5,6].
The total cost is 0 + 0 + 0 + 0 + 1 + 2 = 3.
</pre>

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

<pre>
<strong>Input:</strong> instructions = [1,3,3,3,2,4,2,1,2]
<strong>Output:</strong> 4
<strong>Explanation:</strong> Begin with nums = [].
Insert 1 with cost min(0, 0) = 0, now nums = [1].
Insert 3 with cost min(1, 0) = 0, now nums = [1,3].
Insert 3 with cost min(1, 0) = 0, now nums = [1,3,3].
Insert 3 with cost min(1, 0) = 0, now nums = [1,3,3,3].
Insert 2 with cost min(1, 3) = 1, now nums = [1,2,3,3,3].
Insert 4 with cost min(5, 0) = 0, now nums = [1,2,3,3,3,4].
​​​​​​​Insert 2 with cost min(1, 4) = 1, now nums = [1,2,2,3,3,3,4].
​​​​​​​Insert 1 with cost min(0, 6) = 0, now nums = [1,1,2,2,3,3,3,4].
​​​​​​​Insert 2 with cost min(2, 4) = 2, now nums = [1,1,2,2,2,3,3,3,4].
The total cost is 0 + 0 + 0 + 0 + 1 + 0 + 1 + 0 + 2 = 4.
</pre>

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

<ul>
	<li><code>1 &lt;= instructions.length &lt;= 10<sup>5</sup></code></li>
	<li><code>1 &lt;= instructions[i] &lt;= 10<sup>5</sup></code></li>
</ul>
#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    #define ll long long
    void merge(vector<pair<ll,ll>> &arr, vector<ll> &less, vector<ll> &big, ll l, ll r) {
        ll i = l;
        ll one = 1;
        ll mid = l + (r-l)/2;
        ll j = mid + one;
        
        vector<pair<ll,ll>> temp((r-l+one));
        ll ind = 0;
        while(i <= mid && j <= r) {
            if(arr[i].first > arr[j].first) {
                temp[ind] = arr[j];
                big[arr[j].second] += (mid - i + one);
                less[arr[j].second] += (i - l);
                j++; ind++;
            }
            else if(arr[i].first <= arr[j].first) {
                temp[ind] = arr[i];
                ind++;
                i++;
            }
        }
        while(j <= r) {
            temp[ind] = arr[j];
            less[arr[j].second] += (mid - l + one);
            j++; ind++;
        }
        while(i <= mid) {
            temp[ind] = arr[i];
            ind++;
            i++;
        }
        for (ll i = 0; i < (r-l+one); i++) {
            arr[l+i] = temp[i];
        }
    }
    void mergeSort(vector<pair<ll,ll>> &arr, vector<ll> &less, vector<ll> &big, ll l, ll r) {
        if(l < r) {
            ll mid = l + (r -l)/2;
            mergeSort(arr, less, big, l, mid);
            mergeSort(arr, less, big, mid + 1, r);
            merge(arr,less,big,l,r);
        }
    }
    int createSortedArray(vector<int>& nums) {
        ll n = nums.size();
        vector<pair<ll,ll>> arr(n);
        vector<ll> less(n, 0ll), big(n, 0ll), equal(n, 0ll);
        unordered_map<ll, ll> cnt;
        for (ll i = 0; i < n; i++) {
            equal[i] = cnt[nums[i]];
            cnt[nums[i]]++;
            arr[i] = {nums[i], i};
        }
        ll mod = 1e9 + 7;
        mergeSort(arr,less,big,0,n-1);
        long long ans = 0;
        for (ll i = 0; i < n; i++) {
            // cout << less[i] << " " << big[i] << " " << equal[i] << endl;
            ans += min(less[i] - equal[i], big[i]);
            ans %= mod;
            // if(ans < 0) {
            //     cout << "hi " << ans << endl;
            // }
        }
        return ans;
    }
};
377706