<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>
class Solution {
public:
  void merge(int left,int mid,int right,vector<pair<int,int>>& v,vector<int>&lesser,vector<int>&greater)
  {
    for(int i = mid + 1, j = left, k = left; i <= right; i++) {
            while(j <= mid and v[j].first < v[i].first) j++;
            while(k <= mid and v[k].first <= v[i].first) k++;
            lesser[v[i].second] += j - left;
            greater[v[i].second] += mid - k + 1;
        }
    int n1=mid-left+1;
    int n2=right-mid;
    vector<pair<int,int>>l(n1);
    vector<pair<int,int>>r(n2);
    for(int i=0;i<n1;i++)
    {
       l[i]=v[left+i];
    }
    for(int i=0;i<n2;i++)
    {
        r[i]=v[mid+1+i];
    }
    int l1=0;
    int r1=0;
    int k=left;
    while(l1<n1&&r1<n2)
    {
        if(l[l1].first<r[r1].first)
        {
           v[k]=l[l1];
           l1++;
        }
        else
        {
            v[k]=r[r1];
            r1++;
        }
        k++;
    }
    while(l1<n1)
    {
        v[k]=l[l1];
        l1++;
        k++;
    }
      while(r1<n2)
    {
        v[k]=r[r1];
        r1++;
        k++;
    }
  }
  int mod=1000000007;
   void mergesort(int left,int right,vector<pair<int,int>>& v,vector<int>&lesser,vector<int>&greater)
   {
    if(left>=right)
    {
        return;
    }
    int mid=(left+right)/2;
    mergesort(left,mid,v,lesser,greater);
    mergesort(mid+1,right,v,lesser,greater);
    merge(left,mid,right,v,lesser,greater);
      
   }
    int createSortedArray(vector<int>& instructions) {
        vector<pair<int,int>>v;
        for(int i=0;i<instructions.size();i++)
        {
            v.push_back({instructions[i],i});
        }
        vector<int>lesser(instructions.size(),0);
        vector<int>greater(instructions.size(),0);
       mergesort(0,instructions.size()-1,v,lesser,greater);
  int ans = 0;
        for (int i = 0; i < instructions.size(); i++) {
            // calculate the minimum of the two values and add it to the answer
            ans += min(lesser[i], greater[i]);
            ans %= mod;
        }
       return ans;
    }
};
382018