<p>You are given an array <code>target</code> that consists of <strong>distinct</strong> integers and another integer array <code>arr</code> that <strong>can</strong> have duplicates.</p>

<p>In one operation, you can insert any integer at any position in <code>arr</code>. For example, if <code>arr = [1,4,1,2]</code>, you can add <code>3</code> in the middle and make it <code>[1,4,<u>3</u>,1,2]</code>. Note that you can insert the integer at the very beginning or end of the array.</p>

<p>Return <em>the <strong>minimum</strong> number of operations needed to make </em><code>target</code><em> a <strong>subsequence</strong> of </em><code>arr</code><em>.</em></p>

<p>A <strong>subsequence</strong> of an array is a new array generated from the original array by deleting some elements (possibly none) without changing the remaining elements&#39; relative order. For example, <code>[2,7,4]</code> is a subsequence of <code>[4,<u>2</u>,3,<u>7</u>,2,1,<u>4</u>]</code> (the underlined elements), while <code>[2,4,2]</code> is not.</p>

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

<pre>
<strong>Input:</strong> target = [5,1,3], <code>arr</code> = [9,4,2,3,4]
<strong>Output:</strong> 2
<strong>Explanation:</strong> You can add 5 and 1 in such a way that makes <code>arr</code> = [<u>5</u>,9,4,<u>1</u>,2,3,4], then target will be a subsequence of <code>arr</code>.
</pre>

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

<pre>
<strong>Input:</strong> target = [6,4,8,1,3,2], <code>arr</code> = [4,7,6,2,3,8,6,1]
<strong>Output:</strong> 3
</pre>

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

<ul>
	<li><code>1 &lt;= target.length, arr.length &lt;= 10<sup>5</sup></code></li>
	<li><code>1 &lt;= target[i], arr[i] &lt;= 10<sup>9</sup></code></li>
	<li><code>target</code> contains no duplicates.</li>
</ul>

class Solution:
    def minOperations(self, target: List[int], arr: List[int]) -> int:
        # We want to find the longest common subsequence of target and arr, then len(target) - LCS is the answer.
        # The DP based LCS algorithm has the complexity of O(mn). It is not doable here as m ~ n ~ 10^5.
        # There is another constraint: the elements in the target are distinct. So we can replace the elements in target with 0, 1, 2, ... (a strictly increasing array). Then the problem is converted as finding LIS in arr with respect to the replaced numbers.
        # Patience Game approach can achieve O(nlogn) in finding LIS (while the traditional DP based approach is still O(n^2)).
        rep_dict = {n:i - len(target) for i, n in enumerate(target)}
        for i in range(len(arr)):
            if arr[i] in rep_dict:
                arr[i] = rep_dict[arr[i]]
        piles = []
        for n in arr:
            if n < 0:
                # So it is a replaced element, we need to take it into account in deriving LIS
                i = bisect.bisect_left(piles, n)
                if i == len(piles):
                    piles.append(n)
                else:
                    piles[i] = n
        return len(target) - len(piles)
764