<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:
    class BIT {
    public:
        BIT(int size): n(size), bit(n+1, 0) {}

        void add(int x) {
            for (int i=x; i<=n; i+=lowbit(i)) {
                bit[i]++;
            }
        }

        int count(int x) {
            int sum = 0;
            for (int i=x; i>0; i-=lowbit(i))
                sum += bit[i];
            return sum;
        }
    private:
        int lowbit(int x) {return x & (-x);}
        int n;
        vector<int> bit;
    };
    int MOD = 1e9 + 7;
    int createSortedArray(vector<int>& instructions) {
        set<int> s; // ordered
        for (int k : instructions)
            s.insert(k);
        int idx = 0;
        unordered_map<int,int> mp;
        for (int k : s)
            mp[k] = ++idx;
        
        BIT bit(idx);
        int n = instructions.size();
        int ret = 0;
        for (int i = 0; i < n; i++) {
            int val = mp[instructions[i]];
            int smaller = bit.count(val - 1);
            int larger = i - bit.count(val);
            int cost = min(smaller, larger);
            ret = (ret + cost) % MOD;
            bit.add(val);
        }
        return ret;
    }
};

/**

the problem is closely related to finding #inversion of array

if arr is sorted, cost = 0

In a ascending sorted array a = [1,2,3,4,5]

if a[i] == a[j], cost = 0
swap [2,1,3,4,5], cost=  0
swap [3,2,1,4,5], cost = 0
swap [4,2,3,1,5], cost = 1 

swap [1,5,3,4,2], cost = 3
-: (5,3)(5,4)(5,2)(3,2)(4,2)
+: 
xi , xi+1, xi+2, ... xj

(i-1), xj, xi+1, xi+2, ... ,xj-1, xi,

for xi+1 to xj-1 may introduce min(1, cur-2)
for xi cost = min(i-1, j-i-1)

N = len(instructions), M = #different value
Method1 Segment Tree NlogM
Method2 BIT (adopted NlogM)

*/


192268