<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>

'''
Brute Force - Explore adding each number in target at every index in arr -> O(m2^n) n = target, m = arr

I think the question I need to ask is

- If the first number in target was a 5, and I had it at index 2 or 6, I would always want to pick the one at 2
- BUT if I had 5 and 1, it maybe more worthwhile to pick a 1 that is to the left of 5 because all the other targets may be to the left of the first occurrence
- Then the question becomes kind of simple
    - Start at the start index of each number in target and DFS through, counting how many numbers you can do and subtracting that from len(targets)
    - O(n^2)
    
- How can I improve the O(n^2) solution to O(n)

Isn't this a longest common subsequence problem - but that one is O(n^2) and it's not a deck of cards but more so dp matcfhing on the ending

- this idea of you're either starting a new sequence here or reusing from previous one
- so the deck of cards thing I was confused because if you replace [2 5 8] -> [2 3 8] you can't do [3 8] but the thing is this deck of cards keeps length of the longest...and not the current...so that in the future if putting in the 3 was the correct choice, then you would get the answer. Let's say you get a 9, then it woudl be [2 3 8 9] which wouldn't make sense but would work with the 5...
- also everything to the left of your insert must come before so that's a valid sequence
'''

class Solution:
    def minOperations(self, target: List[int], arr: List[int]) -> int:
        tmp_list = []
        val = {}
        
        v = 0
        for t in target:
            if t not in val:
                val[t] = v
                v += 1
                
        for num in arr:
            if num in val:
                tmp_list.append(val[num])

        deck = []
        for num in tmp_list:
            idx = bisect.bisect_left(deck, num)

            
            if idx == len(deck):
                deck.append(num)
            else:
                if deck[idx] > num:
                    deck[idx] = num
        return len(target) - len(deck)
            
39900