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

import bisect
class Solution:
    def minOperations(self, target: List[int], arr: List[int]) -> int:
        # index의 복수형이 indices래. 처음알았당
        # arr의 원소 값이 target에서 어떤인덱스를 가지는지 담을 리스트.
        # target에 없는 원소는 무시해도 되므로 제외할 예정.
        indices=[]
        # target의 값 : 인덱스 순으로 딕셔너리 만들기.
        t_dic={n:i for i,n in enumerate(target)}
        for n in arr:
            if n in t_dic:
                indices.append(t_dic[n])
        # tail: 최대 길이의 증가하는 인덱스 배열.
        # tail 자체가 최소 원소라는 뜻이다.
        # tails 원소는 오름차순으로 정렬한다. 최대 길이를 찾기 위해 최소 인덱스값을 가진애들로 대체하면서 구한다.
        tails=[]
        for i in indices:
            # 첫번째원소거나 tail의 마지막값(인덱스 중 제일 큰 값)보다 인덱스가 크면 append하기.
            if not tails or tails[-1]<i:
                tails.append(i)
            # 그게 아니면 bisect 모듈로 tail의 어느 인덱스에 i를 넣어야 오름차순 정렬인지 구하고 해당 인덱스를 교환한다. (인덱스를 더 작은값으로 바꿔서 다음에 올 인덱스가 최대가 될 확률을 높인다.)
            else:
                tails[bisect.bisect_left(tails,i)]=i
        return len(target)-len(tails)
697