<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>
RED = False
BLACK = True

class Node:
    def __init__(self, val, colour=RED, parent=None, left=None, right=None):
        self.val = val
        self.count = self.size = 1
        self.colour = colour
        self.parent = parent
        self.left = left
        self.right = right


class RBTree:
    def __init__(self):
        self.root = None
    
    def rotate_left(self, node):
        child = node.right
        node.right = child.left
        if child.left:
            child.left.parent = node
        child.parent = node.parent
        if not node.parent:
            self.root = child
        elif node == node.parent.left:
            node.parent.left = child
        else:
            node.parent.right = child
        node.size -= child.count
        if child.right:
            node.size -= child.right.size
        child.size += node.count
        if node.left:
            child.size += node.left.size
        child.left = node
        node.parent = child

    def rotate_right(self, node):
        child = node.left
        node.left = child.right
        if child.right:
            child.right.parent = node
        child.parent = node.parent
        if not node.parent:
            self.root = child
        elif node == node.parent.right:
            node.parent.right = child
        else:
            node.parent.left = child
        node.size -= child.count
        if child.left:
            node.size -= child.left.size
        child.size += node.count
        if node.right:
            child.size += node.right.size
        child.right = node
        node.parent = child

    def insert(self, val):
        lt = 0
        gt = 0
        node = Node(val)
        if not self.root:
            self.root = node
            return 0
        y = None
        x = self.root
        while x:
            x.size += 1
            y = x
            if val < x.val:
                gt += x.count
                if x.right:
                    gt += x.right.size
                x = x.left
            elif val > x.val:
                lt += x.count
                if x.left:
                    lt += x.left.size
                x = x.right
            else:
                x.count += 1
                if x.left:
                    lt += x.left.size
                if x.right:
                    gt += x.right.size
                return min(lt, gt)
        node.parent = y
        if val < y.val:
            y.left = node
        else:
            y.right = node
        
        # fixup
        while node.parent and node.parent.colour == RED:
            if node.parent.parent and node.parent == node.parent.parent.left:
                y = node.parent.parent.right
                if y and y.colour == RED:
                    y.colour = node.parent.colour = BLACK
                    node.parent.parent.colour = RED
                    node = node.parent.parent
                else:
                    if node == node.parent.right:
                        node = node.parent
                        self.rotate_left(node)
                    node.parent.colour = BLACK
                    node.parent.parent.colour = RED
                    self.rotate_right(node.parent.parent)
            elif node.parent.parent:
                y = node.parent.parent.left
                if y and y.colour == RED:
                    node.parent.colour = BLACK
                    y.colour = BLACK
                    node.parent.parent.colour = RED
                    node = node.parent.parent
                else:
                    if node == node.parent.left:
                        node = node.parent
                        self.rotate_right(node)
                    node.parent.colour = BLACK
                    node.parent.parent.colour = RED
                    self.rotate_left(node.parent.parent)
            else:
                break
        self.root.colour = BLACK
        return min(lt, gt)


class Solution:
    def createSortedArray(self, instructions: List[int]) -> int:
        tot = 0
        tree = RBTree()
        for i in instructions:
            tot = (tot + tree.insert(i)) % 1000000007
        return tot
54000