<p>Given two integer arrays&nbsp;<code>arr1</code> and <code>arr2</code>, return the minimum number of operations (possibly zero) needed&nbsp;to make <code>arr1</code> strictly increasing.</p>

<p>In one operation, you can choose two indices&nbsp;<code>0 &lt;=&nbsp;i &lt; arr1.length</code>&nbsp;and&nbsp;<code>0 &lt;= j &lt; arr2.length</code>&nbsp;and do the assignment&nbsp;<code>arr1[i] = arr2[j]</code>.</p>

<p>If there is no way to make&nbsp;<code>arr1</code>&nbsp;strictly increasing,&nbsp;return&nbsp;<code>-1</code>.</p>

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

<pre>
<strong>Input:</strong> arr1 = [1,5,3,6,7], arr2 = [1,3,2,4]
<strong>Output:</strong> 1
<strong>Explanation:</strong> Replace <code>5</code> with <code>2</code>, then <code>arr1 = [1, 2, 3, 6, 7]</code>.
</pre>

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

<pre>
<strong>Input:</strong> arr1 = [1,5,3,6,7], arr2 = [4,3,1]
<strong>Output:</strong> 2
<strong>Explanation:</strong> Replace <code>5</code> with <code>3</code> and then replace <code>3</code> with <code>4</code>. <code>arr1 = [1, 3, 4, 6, 7]</code>.
</pre>

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

<pre>
<strong>Input:</strong> arr1 = [1,5,3,6,7], arr2 = [1,6,3,3]
<strong>Output:</strong> -1
<strong>Explanation:</strong> You can&#39;t make <code>arr1</code> strictly increasing.</pre>

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

<ul>
	<li><code>1 &lt;= arr1.length, arr2.length &lt;= 2000</code></li>
	<li><code>0 &lt;= arr1[i], arr2[i] &lt;= 10^9</code></li>
</ul>

<p>&nbsp;</p>

class Solution {
public:
    int inf = 10000;
    int lower(vector<int> &a, int val){
        int n = a.size();
        int l=0, r=n-1, mid;
        int ans = -1;
        while(l<=r) {
            mid = (l+r)/2;
            if(a[mid]<val){
                ans = mid;
                l = mid+1;
            }else{
                r = mid-1;
            }
        }
        return ans;
    }
    int makeArrayIncreasing(vector<int>& a, vector<int>& b) {
        int n = a.size();
        
        set<int> st;
        for(int i: b){
            st.insert(i);
        }
        b.clear();
        for(auto i: st){
            b.push_back(i);
        }
        int m = b.size();
        vector<int> dp(m, 1);
        for(int i=0;i<m;i++){
            if(b[i] == a[0]){
                dp[i] = 0;
            }
        }
        vector<int> pre(m);
        pre[0] = dp[0];
        for(int i=1;i<m;i++){
            pre[i] = min(pre[i-1], dp[i]);
        }
        // for(int i=0;i<m;i++){
        //     cout<<dp[i]<<" ";
        // }
        // cout<<endl;
        vector<int> p(n);
        for(int i=1;i<n;i++){
            int in = lower(b, a[i]);
            if(in ==-1){
                p[i] = inf;
            }else{
                p[i] = pre[in];
            }
            if(a[i]> a[i-1]){
                p[i] = min(p[i], p[i-1]);
            }
            // cout<<p[i]<<endl;
            vector<int> new_pre(m);
            for(int j=0;j<m;j++){
                dp[j] = j-1 >=0 ? pre[j-1]+1 : inf;
                if(a[i-1] < b[j]){
                    dp[j] = min(dp[j], 1 + p[i-1]);
                }
                if(b[j] == a[i]){
                    dp[j] = min(dp[j], p[i]);
                }
                new_pre[j] = dp[j];
                if(j-1>=0){
                    new_pre[j] = min(new_pre[j], new_pre[j-1]);
                }
            }
            // for(int i=0;i<m;i++){
            //     cout<<dp[i]<<" ";
            // }
            // cout<<endl;
            pre = new_pre;
        }

        int ans = p[n-1];
        for(int i=0;i<m;i++){
            ans = min(ans, dp[i]);
        }
        return ans > m ? -1: ans;
    }
};
46043