<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>
struct Node {
  Node* lft = NULL;
  Node* rht = NULL;
  int V = 0;
  int S = 0;
  int C = 0;
  Node(int V) {
    this -> V = V;
  }
};
const int mod = 1e9 + 7;
class Solution {
public:
    int createSortedArray(vector<int>& A) {
      auto build = [&] (auto &&build, int L, int R, vector <int> &V) -> Node* {
        if (L > R)
          return NULL;
        int M = (L + R) >> 1;
        Node* root = new Node(V[M]);
        root -> lft = build(build, L, M - 1, V);
        root -> rht = build(build, M + 1, R, V);
        return root;
      };
      auto add = [&] (auto &&add, Node* cur, int v) -> void {
        if (v < cur -> V) 
          add(add, cur -> lft, v);
        else if (v > cur -> V) 
          add(add, cur -> rht, v);
        else 
          cur -> C++;
        cur -> S++;
      };

      set <int> st;
      for (int &a : A)
        st.insert(a);
      vector <int> V;
      for (int x : st)
        V.push_back(x);
      Node* root = build(build, 0, (int) V.size() - 1, V);
      
      int Ans = 0;
      for (int i = 0; i < (int) A.size(); ++i) {
        add(add, root, A[i]);
        Node* cur = root;
        int L = 0, R = 0;
        while (cur -> V != A[i]) {
          if (A[i] < cur -> V) {
            R += (cur -> rht ? cur -> rht -> S : 0) + cur -> C;
            cur = cur -> lft;
          }
          else if (A[i] > cur -> V) {
            L += (cur -> lft ? cur -> lft -> S : 0) + cur -> C;
            cur = cur -> rht;
          }
        }
        L += (cur -> lft ? cur -> lft -> S : 0);
        R += (cur -> rht ? cur -> rht -> S : 0);
        Ans += min(L, R);
        Ans %= mod;
      }
      return Ans;
    }
};
205206