<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 Node{
    public:
    Node* left ;
    Node* right ;
    int s ;
    int e ;
    int cnt ;

    Node(int ss , int ee){
        s = ss ;
        e = ee ;
        cnt = 0 ;
        left = NULL ;
        right = NULL ;
    }
};

class Segment{
    public:
    Node* root ;

    Segment(){
        root = new Node(0 , 1e6);
    }

    void update(Node* node , int index){
        if(node == NULL ) return ; 
        int s = node->s , e = node->e ;

        if( index < s || index > e) return ;

        if(s == e){
            node->cnt += 1 ;
            return ; 
        }

        int mid = s+(e-s)/2 ;
        if(node->left == NULL){
            node->left = new Node(s , mid);
            node->right = new Node(mid+1 , e);
        }

        update(node->left , index) ;
        update(node->right , index);

        node->cnt = node->left->cnt + node->right->cnt ;
        return ;
    }

    int justSmaller(Node* node , int val){
        if(node == NULL ) return 0 ;
        
        int s = node->s , e = node->e ;

        if(s >= val ) return 0 ;
        if(e < val) return node->cnt ;

        if(s == e) {
            return node->cnt ;
        }

        int mid= s+(e-s)/2 ;
        int leftRes = justSmaller(node->left , val);
        int rightRes = justSmaller(node->right , val);

        return leftRes + rightRes ;
    }

    int justGreater(Node* node , int val){
        if(node == NULL ) return 0 ;
        
        int s = node->s , e = node->e ;

        if(e <= val) return 0 ;
        if(s > val) return node->cnt ;

        if(s == e) {
            return node->cnt ;
        }

        int mid= s+(e-s)/2 ;
        int leftRes = justGreater(node->left , val);
        int rightRes = justGreater(node->right , val);

        return leftRes + rightRes ;
    }


};
class Solution {
public:
    int createSortedArray(vector<int>& instructions) {
        Segment seg ;

        long long ans = 0 ;
        int mod = 1e9+7 ;
        for(int i=0;i<instructions.size() ; i++){

            int smaller = seg.justSmaller(seg.root , instructions[i]);
            int greater = seg.justGreater(seg.root , instructions[i]);
            ans += min(smaller , greater);
            ans = ans%mod ;
            seg.update(seg.root , instructions[i]);
        }

        return ans ;
    }
};
209518