<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 {
public:
    int minOperations(vector<int>& target, vector<int>& _arr) {

        int ans = 0;

        unordered_map<int,int> mp;

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

        vector<int> arr;
        for( int val: _arr) {
            if(mp.find(val)!=mp.end()) {
                arr.push_back(mp[val]);
            }
        }

        cout << " ts: " << target.size() << endl;

        cout << " arr: ";
        for( int v: arr) {
            cout << v << " ";
        }
        cout << endl;

        int n = target.size();

        vector<int> st;
        
        function<int(int,int,int,int,int)> query;

        function<void(int,int,int,int,int)> update;

        // resize
        int m = 1;
        while(m<n) {
            m = 2*m;
        }
        st.resize( 2*m, 0);

        query = [&]( int nodeId, int startId, int endId, int l, int r)->int {
            if((l>r) || (startId>endId) || (endId<l) || (r<startId)) {
                return 0;
            } else if((l<=startId) && (endId<=r)) {
                return st[nodeId];
            } else {
                int midId = (startId+endId)/2;
                return max(
                    query( 2*nodeId, startId, midId, l, r),
                    query( 2*nodeId+1, midId+1, endId, l, r)
                );
            }
        };

        update = [&]( int nodeId, int startId, int endId, int pos, int val)->void {
            if(startId==endId) {
                st[nodeId] = max( st[nodeId], val);
            } else {
                int midId = (startId+endId)/2;
                if(pos<=midId) {
                    update( 2*nodeId, startId, midId, pos, val);
                } else {
                    update( 2*nodeId+1, midId+1, endId, pos, val);
                }
                st[nodeId] = max( st[2*nodeId], st[2*nodeId+1]);
            }
        };

        for( int v: arr) {
            int temp = 1+query( 1, 0, n-1, 0, v-1);
            update( 1, 0, n-1, v, temp);
            ans = max( ans, temp);
        }

        return target.size()-ans;
    }
};
121500