<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 <ext/pb_ds/assoc_container.hpp> // Common file
// #include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update
// #include <ext/pb_ds/detail/standard_policies.hpp>
// using namespace __gnu_pbds;

// typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

// class Solution {
// public:
//     const int mod = 1e9+7;
//     int createSortedArray(vector<int>& nums) {
//         ordered_set st1, st2;
//         int ans=0;

//         for(int i=0;i<nums.size();i++){
//             int x = nums[i];
//             int sm = st1.order_of_key(x);
//             int lx = st2.order_of_key(-1*x);
//             // cout<<sm<<" "<<lx<<endl;
//             st1.insert(x);
//             st2.insert(-1*x);
//             ans= (ans+min(sm,lx))%mod;
//         }
//         return ans;
//     }
// };
class Solution {
public:
    const int mod = 1e9+7;
    vector<int> lesser, greater;
    void merge(int left,int mid, int right, vector<pair<int,int>> &v){

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

        vector<pair<int,int>> temp(right - left + 1);
        int i=left,j=mid+1,k=0;

        while(i<=mid && j<=right){
            if(v[i].first<=v[j].first){
                temp[k++]=v[i++];
            }
            else{
                temp[k++]=v[j++];
            }
        }
        while(i<=mid){
            temp[k++]=v[i++];
        }
        while(j<=right){
            temp[k++]=v[j++];
        }
        for(int i=left;i<=right;i++){
            v[i]=temp[i-left];
        }
        // for(auto x: temp){cout<<x.first<<" ";}
        // cout<<endl;
    }
    void mergeSort(int l, int r,vector<pair<int,int>> &v){
        if(l>=r)return;
        int mid = (l+r)/2;
        mergeSort(l, mid,v);
        mergeSort(mid+1, r, v);

        merge(l, mid, r, v);
    }
  
    int createSortedArray(vector<int>& nums) {
        int n= nums.size();
        lesser.resize(n);
        greater.resize(n);

        vector<pair<int,int>> v;
        for(int i=0;i<n;i++){
            v.push_back({nums[i], i});
        }   

        mergeSort(0, n-1, v);

        int ans=0;
        for(int i=0;i<n;i++){
            ans= (ans+min(lesser[i], greater[i]))%mod;
        }
        return ans;
    }
};
351831