<p>You are given an integer array <code>nums</code> containing <strong>distinct</strong> numbers, and you can perform the following operations <strong>until the array is empty</strong>:</p>

<ul>
	<li>If the first element has the <strong>smallest</strong> value, remove it</li>
	<li>Otherwise, put the first element at the <strong>end</strong> of the array.</li>
</ul>

<p>Return <em>an integer denoting the number of operations it takes to make </em><code>nums</code><em> empty.</em></p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> nums = [3,4,-1]
<strong>Output:</strong> 5
</pre>

<table style="border: 2px solid black; border-collapse: collapse;">
	<thead>
		<tr>
			<th style="border: 2px solid black; padding: 5px;">Operation</th>
			<th style="border: 2px solid black; padding: 5px;">Array</th>
		</tr>
	</thead>
	<tbody>
		<tr>
			<td style="border: 2px solid black; padding: 5px;">1</td>
			<td style="border: 2px solid black; padding: 5px;">[4, -1, 3]</td>
		</tr>
		<tr>
			<td style="border: 2px solid black; padding: 5px;">2</td>
			<td style="border: 2px solid black; padding: 5px;">[-1, 3, 4]</td>
		</tr>
		<tr>
			<td style="border: 2px solid black; padding: 5px;">3</td>
			<td style="border: 2px solid black; padding: 5px;">[3, 4]</td>
		</tr>
		<tr>
			<td style="border: 2px solid black; padding: 5px;">4</td>
			<td style="border: 2px solid black; padding: 5px;">[4]</td>
		</tr>
		<tr>
			<td style="border: 2px solid black; padding: 5px;">5</td>
			<td style="border: 2px solid black; padding: 5px;">[]</td>
		</tr>
	</tbody>
</table>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> nums = [1,2,4,3]
<strong>Output:</strong> 5
</pre>

<table style="border: 2px solid black; border-collapse: collapse;">
	<thead>
		<tr>
			<th style="border: 2px solid black; padding: 5px;">Operation</th>
			<th style="border: 2px solid black; padding: 5px;">Array</th>
		</tr>
	</thead>
	<tbody>
		<tr>
			<td style="border: 2px solid black; padding: 5px;">1</td>
			<td style="border: 2px solid black; padding: 5px;">[2, 4, 3]</td>
		</tr>
		<tr>
			<td style="border: 2px solid black; padding: 5px;">2</td>
			<td style="border: 2px solid black; padding: 5px;">[4, 3]</td>
		</tr>
		<tr>
			<td style="border: 2px solid black; padding: 5px;">3</td>
			<td style="border: 2px solid black; padding: 5px;">[3, 4]</td>
		</tr>
		<tr>
			<td style="border: 2px solid black; padding: 5px;">4</td>
			<td style="border: 2px solid black; padding: 5px;">[4]</td>
		</tr>
		<tr>
			<td style="border: 2px solid black; padding: 5px;">5</td>
			<td style="border: 2px solid black; padding: 5px;">[]</td>
		</tr>
	</tbody>
</table>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> nums = [1,2,3]
<strong>Output:</strong> 3
</pre>

<table style="border: 2px solid black; border-collapse: collapse;">
	<thead>
		<tr>
			<th style="border: 2px solid black; padding: 5px;">Operation</th>
			<th style="border: 2px solid black; padding: 5px;">Array</th>
		</tr>
	</thead>
	<tbody>
		<tr>
			<td style="border: 2px solid black; padding: 5px;">1</td>
			<td style="border: 2px solid black; padding: 5px;">[2, 3]</td>
		</tr>
		<tr>
			<td style="border: 2px solid black; padding: 5px;">2</td>
			<td style="border: 2px solid black; padding: 5px;">[3]</td>
		</tr>
		<tr>
			<td style="border: 2px solid black; padding: 5px;">3</td>
			<td style="border: 2px solid black; padding: 5px;">[]</td>
		</tr>
	</tbody>
</table>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>
	<li><code>-10<sup>9&nbsp;</sup>&lt;= nums[i] &lt;= 10<sup>9</sup></code></li>
	<li>All values in <code>nums</code> are <strong>distinct</strong>.</li>
</ul>

class BIT_Tree: 
  def __init__(self, size):
    self.tree = [0 for _ in range(size+1)]

  # because -i is the two's complement (inverse of i + 1) --> all bits greater than RSB = opposite, all bits less than RSB = 0 
  def find_rsb(self, i):
    return i & -i 

  # i = idx in the nums array 
  def update(self, idx, val):
    idx += 1
    while idx < len(self.tree): 
      self.tree[idx] += val
      idx += self.find_rsb(idx)

  # idx is idx in arr
  def prefix_sum(self, idx):
    # tree idx = arr idx + 1 
    idx += 1
    sum = 0 
    while idx > 0: 
      sum += self.tree[idx]
      idx -= self.find_rsb(idx)
    return sum

  def range_query(self, left, right):
    return self.prefix_sum(right) - self.prefix_sum(left-1)

class Solution:
    def countOperationsToEmptyArray(self, nums: List[int]) -> int:
        sorted_arr_positions = sorted(range(len(nums)), key=lambda x: nums[x])
        print(sorted_arr_positions)
        BIT = BIT_Tree(len(sorted_arr_positions))

        ans = 0 
        curr_idx = 0 
        for pos_smallest in sorted_arr_positions: 
            if curr_idx <= pos_smallest:
                # num of steps from curr_idx to pos_smallest, +1 for removal of pos_smallest itself
                ans += (pos_smallest - curr_idx) - (BIT.range_query(curr_idx, pos_smallest-1)) + 1 # getting updated distance
                # getting updated idx's: ans += (pos_smallest - BIT.prefix_sum(pos_smallest)) - (curr_idx - BIT.prefix_sum(curr_idx-1)) + 1
            else: 
                # num steps from curr_idx to end + num steps to pos_smallest +1 for removal of pos_smallest
                ans += (len(nums) - curr_idx) - (BIT.range_query(curr_idx, len(nums)-1)) + (pos_smallest - BIT.range_query(0, pos_smallest-1)) + 1
                # ans += (len(nums) - BIT.prefix_sum(len(nums)-1)) - (curr_idx - BIT.prefix_sum(curr_idx-1)) + (pos_smallest - BIT.prefix_sum(pos_smallest-1)) + 1

            BIT.update(pos_smallest, 1)
            curr_idx = pos_smallest

        return ans

                

                
31500