<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>
#include <vector>
#include <unordered_map>
#include <algorithm>

using std::vector;
using std::unordered_map;

namespace cust			//customized / non-standard
{
	class segment_tree
	{
		public:
			segment_tree(int n) : n { n }
			{
				impl.assign(2 * n - 1, 0);
			}

			void update(int idx)
			{
				if (0 <= idx && idx < n)
					update(idx, 0, n - 1, 0);
			}

			int query(int left, int right) const
			{
				return 0 <= left && left <= right && right < n ? query(left, right, 0, n - 1, 0) : 0;
			}

		private:
			void update(int idx, int idxL, int idxR, int pos)
			{
				++impl[pos];

				if (idxL < idxR)
				{
					auto idxM { idxL + (idxR - idxL) / 2 };

					if (idx <= idxM)
						update(idx, idxL,     idxM, pos + 1);
					else
						update(idx, idxM + 1, idxR, pos + 2 * (idxM - idxL + 1));
				}
			}

			int query(int left, int right, int idxL, int idxR, int pos) const
			{
				auto idxM { idxL + (idxR - idxL) / 2 };

				if (left == idxL && right == idxR)
					return impl[pos];
				else if (right <= idxM)
					return query(left, right, idxL,     idxM, pos + 1);
				else if (idxM < left)
					return query(left, right, idxM + 1, idxR, pos + 2 * (idxM - idxL + 1));
				else
					return query(left, idxM, idxL, idxM, pos + 1) + query(idxM + 1, right, idxM + 1, idxR, pos + 2 * (idxM - idxL + 1));
			}

			const int n;

			vector<int> impl {};
	};
}

class Solution
{
	public:
		int createSortedArray(vector<int>& instructions)
		{
			unordered_map<int, int> umap {};
			vector<int> sorted {};
			long long total_cost { 0LL };

			for(auto num : instructions)
				umap.emplace(num, 0);

			sorted.reserve(umap.size());

			for(const auto& pr : umap)
				sorted.push_back(pr.first);

			std::sort(sorted.begin(), sorted.end());

			for(int i { 0 }; i < sorted.size(); ++i)
				umap[sorted[i]] = i;

			cust::segment_tree seg_tree(sorted.size());

			for(auto num : instructions)
			{
				auto idx { umap[num] };

				total_cost += std::min(seg_tree.query(0, idx - 1), seg_tree.query(idx + 1, sorted.size() - 1));

				seg_tree.update(idx);
			}

			return static_cast<int>(total_cost % 1000000007LL);
		}
};

183643