<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>
/* Segment Tree 
Use of each segment tree leaf node to represent a number in instructions, the info of these leaf nodes are the count of their appearence so far when iterating through the instructions array.

### Implementation Walkthrough
1. **Initialization and Preprocessing:**
   - Convert the `instructions` array into a sorted set `st` to remove duplicates and create a mapping from each element to its index in the sorted set (`num2idx`).
   - Initialize a segment tree (`SegTreeNode` class) to keep track of the counts of elements as they are inserted.
2. **Segment Tree Node (`SegTreeNode`):**
   - Represents a node in the segment tree, with `start` and `end` indicating the range it covers.
   - `info` stores the count of elements within the range represented by the node.
   - Pointers to left and right child nodes.
3. **Initialization (`init`):**
   - Recursively initialize the segment tree with `info` set to 0, representing no elements have been processed initially.
4. **Update (`updateSingleBy`):**
   - Updates the segment tree by incrementing the count of the element at index `idx` by `val` (usually 1).
   - Recursively updates the counts in the segment tree nodes.
5. **Query (`queryRange`):**
   - Queries the segment tree to count the number of elements within a range `[a, b]`.
   - This function is used to find the number of elements smaller or larger than a given element.
6. **Main Logic (`createSortedArray`):**
   - For each element in `instructions`, calculate the cost of inserting it by querying the number of smaller and larger elements already processed.
   - Update the result with the minimum of these two counts, modulo `M` (1e9+7).
   - Update the segment tree to include the current element.

### Key Ideas
- **Segment Tree:** Used for efficiently counting the number of elements in a range.
- **Discrete Mapping:** Maps elements to indices in a sorted set to handle potential large values and facilitate the use of the segment tree.
- **Counting Inversions:** The problem boils down to counting inversions in the array, which is efficiently handled by the segment tree.

### Time Complexity
- **O(n log n):** The segment tree operations (update and query) each take O(log n) time, and they are performed for each of the `n` elements in the `instructions` array.

### Space Complexity
- **O(n):** The space complexity is dominated by the segment tree and the auxiliary data structures like `num2idx` map, both of which have sizes proportional to the number of unique elements in the `instructions` array.

### Optimization
The current implementation is efficient for the problem constraints, leveraging the segment tree's capability to handle range queries and updates efficiently. However, the code could be further optimized or simplified in terms of structure, particularly by:

- **Lazy Propagation:** If the problem included range updates, lazy propagation could be used to optimize update operations.
Given the specific problem requirements, the current solution is appropriately optimized and does not require further modifications.
*/
class Solution {
public:
    int createSortedArray(vector<int>& instructions) {
        // Convert the instruction array to a sorted set, remove duplicate
        set<int> st(instructions.begin(), instructions.end());
        unordered_map<int,int>num2idx;
        int i = 0;
        for (auto x:st)
        {
            num2idx[x] = i;
            i++;
        }
        int n = num2idx.size();
                
        SegTreeNode* root = new SegTreeNode(0, n-1);
        init(root, 0, n-1);
        
        long ret = 0;        
        for (auto x: instructions)
        {
            long a = queryRange(root, 0, num2idx[x]-1);
            long b = queryRange(root, num2idx[x]+1, n-1);
            ret += min(a,b);
            ret %= M;
            updateSingleBy(root, num2idx[x], 1);
        }
        return ret;        
    }

private:
    const long M = 1e9+7;
    class SegTreeNode {
    public:
        SegTreeNode* left;
        SegTreeNode* right;
        int start, end;
        // info represents the count of leaf node that has appeared so far
        int info;        
        SegTreeNode(int a, int b):start(a),end(b),info(0),left(nullptr),right(nullptr){}
    };
    
    // Init info of all nodes to 0
    void init(SegTreeNode* node, int a, int b)
    {                        
        if (a == b) {
            // When there is no element, init node->info to be 0
            node->info = 0;
            return;
        }
        int mid = a + ((b - a) >> 1);
        if (node->left == nullptr) {
            node->left = new SegTreeNode(a, mid);
            node->right = new SegTreeNode(mid + 1, b);
        }
        init(node->left, a, mid);
        init(node->right, mid + 1, b);
                
        node->info = node->left->info + node->right->info;
    }
    
    // Update the info of each leaf node, id should be the index of the current iterated number in the sorted set
    void updateSingleBy(SegTreeNode* node, int idx, int val)
    {        
        if (idx < node->start || idx > node->end) return;
        if (node->start == node->end) {
            node->info += val;
            return;
        }
        updateSingleBy(node->left, idx, val);
        updateSingleBy(node->right, idx, val);
        node->info = node->left->info + node->right->info;
    }
    
    // Based on the populated leaf node so far, calculate total smaller or larger node number
    int queryRange(SegTreeNode* node, int a, int b)
    {
        if (b < node->start || a > node->end) {
            return 0;  
        }
        if (a <= node->start && b>=node->end) {
            return node->info; 
        }        
        return queryRange(node->left, a, b) + queryRange(node->right, a, b); 
    }        
};
287143