Given two integer arrays arr1 and arr2, return the minimum number of operations (possibly zero) needed to make arr1 strictly increasing.
In one operation, you can choose two indices 0 <= i < arr1.length and 0 <= j < arr2.length and do the assignment arr1[i] = arr2[j].
If there is no way to make arr1 strictly increasing, return -1.
 
Example 1:
Input: arr1 = [1,5,3,6,7], arr2 = [1,3,2,4]
Output: 1
Explanation: Replace 5 with 2, then arr1 = [1, 2, 3, 6, 7].

Example 2:
Input: arr1 = [1,5,3,6,7], arr2 = [4,3,1]
Output: 2
Explanation: Replace 5 with 3 and then replace 3 with 4. arr1 = [1, 3, 4, 6, 7].

Example 3:
Input: arr1 = [1,5,3,6,7], arr2 = [1,6,3,3]
Output: -1
Explanation: You can't make arr1 strictly increasing.
 
Constraints:

1 <= arr1.length, arr2.length <= 2000
0 <= arr1[i], arr2[i] <= 10^9

Difficulty: interview

Starter code:

class Solution:
    def makeArrayIncreasing(self, arr1: List[int], arr2: List[int]) -> int:
        

Solutions:
import bisect
from functools import lru_cache


class Solution:
    def makeArrayIncreasing(self, A: List[int], B: List[int]) -> int:
        B = sorted(set(B))

        @lru_cache(None)
        def find_larger_value_in_B(val):
            if val >= B[-1]:
                return float('inf')
            return B[bisect.bisect_right(B, val)]

        @lru_cache(None)
        def min_last_value_given_operations(n, ops):
            if ops < 0:
                return float('inf')
            elif n == 0:
                return float('-inf')
            elif ops > n:
                return min_last_value_given_operations(n, n)

            prev_with_op = min_last_value_given_operations(n - 1, ops - 1)
            b = find_larger_value_in_B(prev_with_op)
            # dp(n - 1, ops) <= dp(n - 1, ops - 1)
            # if dp(n - 1, ops - 1) < A[n - 1] => dp(n - 1, ops) < A[n - 1]
            if prev_with_op < A[n - 1]:
                return min(A[n - 1], b)
            elif b <= A[n - 1]:
                return b
            elif min_last_value_given_operations(n - 1, ops) < A[n - 1]:
                return A[n - 1]
            return b

        last_success = -1
        for ops in range(min(len(A), len(B)), -1, -1):
            if min_last_value_given_operations(len(A), ops) == float('inf'):
                break
            last_success = ops

        return last_success


class Solution:
    def makeArrayIncreasing(self, arr1: List[int], arr2: List[int]) -> int:
        from bisect import bisect_right as br
        arr2.sort()
        
        dp = {0:-math.inf}
        # min_cnt = 0
        for n1 in arr1:
            # print(n1)
            new_dp = {}
            # cnt = min_cnt
            for cnt in dp:
                if n1 > dp[cnt]:
                    new_dp[cnt] = min(new_dp.get(cnt, math.inf), n1)
                i2 = br(arr2, dp[cnt])
                if i2 < len(arr2):
                    new_dp[cnt+1] = min(new_dp.get(cnt+1, math.inf), arr2[i2])
                cnt += 1
            if len(new_dp) == 0:
                return -1
            # while min_cnt not in new_dp:
            #     min_cnt += 1
            dp = new_dp
            # print(dp)
        return min(dp.keys())


class Solution:
    def makeArrayIncreasing(self, arr1: List[int], arr2: List[int]) -> int:
        arr2 = list(set(arr2))
        arr2.sort()
        m, n = len(arr1), len(arr2)
        keep = [float('inf')]*m
        swap = [[float('inf') for _ in range(n)] for _ in range(m)]
        keep[0] = 0
        for i in range(n):
            swap[0][i] = 1
        for i in range(1, m):
            min_keep, min_swap = float('inf'), float('inf')
            for j in range(n):
                if j > 0:
                    min_swap = min(min_swap, swap[i-1][j-1]+1)
                if arr1[i] > arr2[j]:
                    min_keep = min(min_keep, swap[i-1][j])
                if arr1[i] > arr1[i-1]:
                    keep[i] = keep[i-1]
                if arr2[j] > arr1[i-1]:
                    swap[i][j] = keep[i-1]+1
                keep[i] = min(keep[i], min_keep)
                swap[i][j] = min(swap[i][j], min_swap)
        s = float('inf')
        for i in range(n):
            s = min(s, swap[m-1][i])
        res = min(s, keep[m-1])
        return -1 if res >= float('inf') else res

# 见花花酱视频：https://www.bilibili.com/video/av67133426/?spm_id_from=333.788.b_636f6d6d656e74.7
                    
        


import numpy as np


class Solution:
    def makeArrayIncreasing(self, arr1: List[int], arr2: List[int]) -> int:
        m = len(arr1)
        arr2 = sorted(np.unique(arr2))
        n = len(arr2)
        
        keep = [float('inf')] * m
        keep[0] = 0
        swap = [1] * n
        
        for i in range(1, m):
            min_keep = float('inf')
            min_swap = float('inf')
            temp = [float('inf')] * n
            for j in range(n):
                if j > 0:
                    min_swap = min(min_swap, swap[j - 1] + 1)
                if arr1[i] > arr2[j]:
                    min_keep = min(min_keep, swap[j])
                if arr1[i] > arr1[i - 1]:
                    keep[i] = keep[i - 1]
                if arr2[j] > arr1[i - 1]:
                    temp[j] = keep[i - 1] + 1
                temp[j] = min(temp[j], min_swap)
                keep[i] = min(keep[i], min_keep)
            for j in range(n):
                temp[j], swap[j] = swap[j], temp[j]
        
        s = min(swap)
        k = keep[-1]
        ans = min(s, k)
        return ans if ans < float('inf') else -1
        


class Solution:
    def makeArrayIncreasing(self, arr1: List[int], arr2: List[int]) -> int:
        m = len(arr1)
        arr2 = list(set(arr2))
        arr2.sort()
        n = len(arr2)
        keep = [float('inf')] * m
        keep[0] = 0
        swap = [[float('inf') for j in range(n)] for i in range(m)]
        for j in range(n):
            swap[0][j] = 1
        for i in range(1,m):
            min_keep = float('inf')
            min_swap = float('inf')
            for j in range(0, n):
                if j > 0:
                    min_swap = min(min_swap, swap[i-1][j-1] + 1 )
                if arr1[i] > arr2[j]:
                    min_keep = min(min_keep, swap[i-1][j]  )
                if arr1[i] > arr1[i-1]:
                    keep[i] = keep[i -1]
                if arr2[j] > arr1[i-1]:
                    swap[i][j] = keep[i -1] + 1
                swap[i][j] = min(swap[i][j], min_swap)
                keep[i]  = min(keep[i], min_keep )
        
        k = keep[-1]
        min_swap = min(swap[-1])
        ans = min (min_swap, k)
        return ans if ans < float('inf') else -1

from bisect import bisect

class Solution:
    def makeArrayIncreasing(self, arr1: List[int], arr2: List[int]) -> int:
        d = {float('-inf'): 0}
        arr2 = sorted(set(arr2))
        for i in arr1:
            d2 = {}
            for k, v in list(d.items()):
                if i > k:
                    if i in d2:
                        d2[i] = min(d2[i], v)
                    else:
                        d2[i] = v

                if k < arr2[-1]:
                    j = arr2[bisect(arr2, k)]
                    if j in d2:
                        d2[j] = min(d2[j], v + 1)
                    else:
                        d2[j] = v + 1
            
            d = d2
        
        if d:
            return min(d.values())
        return -1
                        
        
        
        
        


from collections import defaultdict
from math import inf
from bisect import bisect_right


class Solution:
    def makeArrayIncreasing(self, arr1: List[int], arr2: List[int]) -> int:
        arr2.sort()
        n = len(arr2)
        dp = {-1: 0}
        for i in arr1:
            next_dp = defaultdict(lambda: inf)
            for key in dp:
                if i > key:
                    next_dp[i] = min(next_dp[i], dp[key])
                loc = bisect_right(arr2, key)
                if loc < n:
                    next_dp[arr2[loc]] = min(next_dp[arr2[loc]], dp[key] + 1)
            dp = next_dp

        return min(dp.values()) if dp else -1

class Solution:
    def makeArrayIncreasing(self, arr1: List[int], arr2: List[int]) -> int:
        from bisect import bisect_right as br
        arr2.sort()
        
        dp = {0:-math.inf}
        min_cnt = 0
        for n1 in arr1:
            # print(n1)
            new_dp = {}
            cnt = min_cnt
            while cnt in dp:
                if n1 > dp[cnt]:
                    new_dp[cnt] = min(new_dp.get(cnt, math.inf), n1)
                    # candidate = min(new_dp.get(cnt, math.inf), n1)
                    # if candidate < new_dp.get(cnt-1, math.inf):
                    #     new_dp[cnt] = candidate
                i2 = br(arr2, dp[cnt])
                # if i2 < len(arr2) and arr2[i2] < new_dp.get(cnt, math.inf):
                if i2 < len(arr2):
                    new_dp[cnt+1] = arr2[i2]
                # print(new_dp)
                # if new_dp.get(cnt+1, -math.inf) >= new_dp.get(cnt, math.inf):
                #     new_dp.pop(cnt+1)
                # if new_dp.get(cnt, -math.inf) >= new_dp.get(cnt-1, math.inf):
                #     new_dp.pop(cnt)
                cnt += 1
            if len(new_dp) == 0:
                return -1
            while min_cnt not in new_dp:
                min_cnt += 1
            dp = new_dp
            print(dp)
        return min(dp.keys())


class Solution:
    def makeArrayIncreasing(self, arr1: List[int], arr2: List[int]) -> int:
        import bisect
        # dp存储所有潜在的当前状态（每次dp都是遍历arr1时前一个位置的状态）
        # 这里的状态是一个键值对，key代表当前位置的数字，
        # 可以是arr1里面的，也可以是arr2里面用来替换的
        # value就是我们需要操作的次数
        dp = {-1: 0}
        arr2.sort()
        for i in arr1:
            tmp = collections.defaultdict(lambda: float('inf'))
            for key in dp:
                if i > key:
                    tmp[i] = min(tmp[i], dp[key])
                loc = bisect.bisect_right(arr2, key)
                if loc < len(arr2):
                    tmp[arr2[loc]] = min(tmp[arr2[loc]], dp[key] + 1)
            dp = tmp
        return min(dp.values()) if dp else -1


from bisect import bisect_right as br
import math
import functools
class Solution:
    def makeArrayIncreasing(self, arr1: List[int], arr2: List[int]) -> int:
        arr2 = sorted(set(arr2))
        @lru_cache(None)
        def dfs(i, prev):
            if i == len(arr1): return 0
            j = br(arr2, prev)
            swap = 1 + dfs(i+1, arr2[j]) if j < len(arr2) else math.inf
            noswap = dfs(i+1, arr1[i]) if prev < arr1[i] else math.inf
            return min(swap, noswap)  
        ret = dfs(0, -math.inf)
        return ret if ret != math.inf else -1
        
        
        
        
        
        # arr2=sorted(set(arr2))
        # @functools.lru_cache(None)
        # def dfs(i,prev):
        #     if i >= len(arr1):
        #         return 0
        #     j = br(arr2,prev)
        #     swap = 1 + dfs(i+1, arr2[j]) if j < len(arr2) else math.inf
        #     noswap = dfs(i+1, arr1[i]) if arr1[i] > prev else math.inf
        #     return min(swap,noswap)
        # changes=dfs(0, -math.inf)
        # return changes if changes!=math.inf else -1


from bisect import bisect_right as br
import math
import functools
class Solution:
    def makeArrayIncreasing(self, arr1: List[int], arr2: List[int]) -> int:
        arr2 = sorted(set(arr2))   
        @lru_cache(None)
        def dfs(i, prev):
            if i >= len(arr1): return 0
            j = br(arr2, prev)
            swap = 1 + dfs(i+1, arr2[j]) if j < len(arr2) else math.inf
            noswap = dfs(i+1, arr1[i]) if prev < arr1[i] else math.inf
            return min(swap, noswap)
        ans = dfs(0, -1)
        return ans if ans != math.inf else -1
        
        
        
        
        # arr2=sorted(set(arr2))
        # @functools.lru_cache(None)
        # def dfs(i,prev):
        #     if i >= len(arr1):
        #         return 0
        #     j = br(arr2,prev)
        #     swap = 1 + dfs(i+1, arr2[j]) if j < len(arr2) else math.inf
        #     noswap = dfs(i+1, arr1[i]) if arr1[i] > prev else math.inf
        #     return min(swap,noswap)
        # changes=dfs(0, -math.inf)
        # return changes if changes!=math.inf else -1


import bisect
from functools import lru_cache


class Solution:
    def makeArrayIncreasing(self, A: List[int], B: List[int]) -> int:
        B = sorted(set(B))

        @lru_cache(None)
        def find_larger_value_in_B(val):
            if val >= B[-1]:
                return float('inf')
            return B[bisect.bisect_right(B, val)]

        @lru_cache(None)
        def min_last_value_given_operations(n, ops):
            if ops < 0:
                return float('inf')
            elif n == 0:
                return float('-inf')
            elif ops > n:
                return min_last_value_given_operations(n, n)

            skip_op = min_last_value_given_operations(n - 1, ops)
            if skip_op == float('inf'):
                return float('inf')
            return min(
                A[n - 1] if skip_op < A[n - 1] else float('inf'),
                find_larger_value_in_B(min_last_value_given_operations(n - 1, ops - 1)),
            )

        last_success = -1
        for ops in range(min(len(A), len(B)), -1, -1):
            if min_last_value_given_operations(len(A), ops) == float('inf'):
                break
            last_success = ops

        return last_success


class Solution:
    def makeArrayIncreasing(self, arr1: List[int], arr2: List[int]) -> int:
        import bisect
        dp = {-1: 0}
        arr2.sort()
        for i in arr1:
            tmp = collections.defaultdict(lambda: float('inf'))
            for key in dp:
                if i > key:
                    tmp[i] = min(tmp[i], dp[key])
                loc = bisect.bisect_right(arr2, key)
                if loc < len(arr2):
                    tmp[arr2[loc]] = min(tmp[arr2[loc]], dp[key] + 1)
            dp = tmp
        return min(dp.values()) if dp else -1


import bisect
import functools
    
class Solution:
    def makeArrayIncreasing(self, arr1: List[int], arr2: List[int]) -> int:
        arr2=sorted(set(arr2))
        
        @functools.lru_cache(None)
        def dfs(i,prev):
            if i>=len(arr1):
                return 0
            j=bisect.bisect_right(arr2,prev)
            swap=1+dfs(i+1,arr2[j]) if j<len(arr2) else math.inf
            noswap=dfs(i+1,arr1[i]) if arr1[i]>prev else math.inf
            return min(swap,noswap)
        changes=dfs(0,-math.inf)
        return changes if changes!=math.inf else -1

from bisect import bisect_right as br
import functools
class Solution:
    def makeArrayIncreasing(self, arr1: List[int], arr2: List[int]) -> int:
        arr2 = sorted(set(arr2))
        @lru_cache(None)
        def dfs(i, prev):
            if i >= len(arr1): return 0
            j = br(arr2, prev)
            swap = 1 + dfs(i+1, arr2[j]) if j < len(arr2) else math.inf
            noswap = dfs(i+1, arr1[i]) if arr1[i] > prev else math.inf
            return min(swap, noswap)
        
        
        ans = dfs(0, -math.inf)
        return ans if ans!=math.inf else -1
        
        
        
        
        
        
        # arr2=sorted(set(arr2))
        # @functools.lru_cache(None)
        # def dfs(i,prev):
        #     if i >= len(arr1):
        #         return 0
        #     j = br(arr2,prev)
        #     swap = 1 + dfs(i+1, arr2[j]) if j < len(arr2) else math.inf
        #     noswap = dfs(i+1, arr1[i]) if arr1[i] > prev else math.inf
        #     return min(swap,noswap)
        # changes=dfs(0, -math.inf)
        # return changes if changes!=math.inf else -1


import bisect
import functools
class Solution:
    def makeArrayIncreasing(self, arr1: List[int], arr2: List[int]) -> int:
        arr2=sorted(set(arr2))
        @functools.lru_cache(None)
        def dfs(i,prev):
            if i>=len(arr1):
                return 0
            j=bisect.bisect_right(arr2,prev)
            swap=1+dfs(i+1,arr2[j]) if j<len(arr2) else math.inf
            noswap=dfs(i+1,arr1[i]) if arr1[i]>prev else math.inf
            return min(swap,noswap)
        changes=dfs(0,-math.inf)
        return changes if changes!=math.inf else -1

import bisect
import functools
    
class Solution:
    def makeArrayIncreasing(self, arr1: List[int], arr2: List[int]) -> int:
        # arr1i
        # arr2j
        arr2 = sorted(set(arr2))
        @functools.lru_cache(None)
        def dfs(prev, i):
            if i == len(arr1):
                return 0
            j = bisect.bisect_right(arr2, prev)
            swap = 1 + dfs(arr2[j], i+1) if j < len(arr2) else float('inf')
            noswap = dfs(arr1[i], i+1) if prev < arr1[i] else float('inf')
            return min(swap, noswap)
        changes = dfs(float('-inf'), 0)
        return changes if changes != float('inf') else -1


class Solution:
  def makeArrayIncreasing(self, arr1: List[int], arr2: List[int]) -> int:
    # TC: O(min(M, N)*N+MlogM), SC: O(min(M, N))
    m, n = len(arr1), len(arr2)
    # sort O(MlogM)
    arr2.sort()
    # maintain a list of (num-of-swaps, last-value, next-to-swap-index-arr2),
    # where the last value should be decrease as the num of swaps is increase
    ss = [(0, arr1[0], 0)]
    if arr2[0] < arr1[0]:
      ss.append((1, arr2[0], 1))
    # O(N) iteration
    for i in range(1, m):
      st = []
      # O(min(M, N))
      for s, x, j in ss:
        if x < arr1[i]:
          if st:
            if s == st[-1][0]:
              if arr1[i] < st[-1][1]:
                st[-1] = (s, arr1[i], j)
            elif s > st[-1][0]:
              if arr1[i] < st[-1][1]:
                st.append((s, arr1[i], j))
          else:
            st.append((s, arr1[i], j))
        # amortized O(1)
        while j < n and arr2[j] <= x:
          j += 1
        if j < n:
          st.append((s + 1, arr2[j], j))
      # since each swap takes at most 1 entry, and at most O(min(M, N)) swap, so SC: O(min(M, N))
      ss = st
    return ss[0][0] if ss else -1

import bisect
from typing import List
from functools import lru_cache


class Solution:
    def makeArrayIncreasing(self, arr1: List[int], arr2: List[int]) -> int:
        array = arr1
        replace = list(sorted(set(arr2)))

        @lru_cache(None)
        def dfs(array_pos: int, prev_number: int) -> int:
            min_replacements = len(replace) * 2

            if array_pos == len(array):
                return 0

            next_replace_pos = 0

            if array_pos > 0:
                next_replace_pos = bisect.bisect(replace, prev_number)

            if array_pos == 0 or (
                next_replace_pos < len(replace)
            ):
                tmp = array[array_pos]
                min_replacements = min(min_replacements, dfs(array_pos + 1, replace[next_replace_pos]) + 1)

            if array_pos == 0 or prev_number < array[array_pos]:
                min_replacements = min(min_replacements, dfs(array_pos + 1, array[array_pos]))

            return min_replacements

        result = dfs(0, -100)

        if result > len(replace):
            return -1

        return result


import bisect
from functools import lru_cache


class Solution:
    def makeArrayIncreasing(self, A: List[int], B: List[int]) -> int:
        B = sorted(set(B))
        b2idx = {b: i for i, b in enumerate(B)}
        
        @lru_cache(None)
        def find_larger_value_in_B(val):
            if val >= B[-1]:
                return float('inf')
            if val in b2idx:
                return B[b2idx[val] + 1]
            return B[bisect.bisect_right(B, val)]

        @lru_cache(None)
        def min_last_value_given_operations(n, ops):
            if ops < 0:
                return float('inf')
            elif n == 0:
                return float('-inf')
            elif ops > n:
                return min_last_value_given_operations(n, n)

            skip_op = min_last_value_given_operations(n - 1, ops)
            if skip_op == float('inf'):
                return float('inf')
            return min(
                A[n - 1] if skip_op < A[n - 1] else float('inf'),
                find_larger_value_in_B(min_last_value_given_operations(n - 1, ops - 1)),
            )

        last_success = -1
        for ops in range(min(len(A), len(B)), -1, -1):
            if min_last_value_given_operations(len(A), ops) == float('inf'):
                break
            last_success = ops

        return last_success


import bisect
import functools
class Solution:
    def makeArrayIncreasing(self, arr1: List[int], arr2: List[int]) -> int:
        arr2=sorted(set(arr2))
        @functools.lru_cache(None)
        def dfs(i,prev):
            if i>=len(arr1):
                return 0
            j = bisect.bisect_right(arr2,prev)
            swap = 1 + dfs(i+1,arr2[j]) if j < len(arr2)  else math.inf
            noswap = dfs(i+1,arr1[i])   if arr1[i] > prev else math.inf
            return min(swap,noswap)
        changes = dfs(0,-math.inf)
        return changes if changes != math.inf else -1


import bisect

class Solution:
    def makeArrayIncreasing(self, arr1: List[int], arr2: List[int]) -> int:
        N = len(arr1)
        arr1 = [0] + arr1
        # 表示前 i 个元素，执行了 k 次操作后，是有序的
        dp = [[float('inf')] * (N + 1) for _ in range(N + 1)]
        dp[0][0] = -float('inf')
        
        arr2.sort()
        for i in range(1, N + 1):
            for k in range(i + 1):
                # 前i-1个元素，已经完成了k次交换
                if arr1[i] > dp[i-1][k]:
                    dp[i][k] = min(dp[i][k], arr1[i])
                
                # 前 i-1 个元素，已经完成了 k-1次交换，所以这一次一定要交换
                if k >= 1:
                    idx_2 = bisect.bisect_right(arr2, dp[i-1][k-1])
                    if idx_2 != len(arr2):                    
                        dp[i][k] = min(dp[i][k], arr2[idx_2])
        
        res = float('inf')
        for i in range(1, N+1):
            if dp[N][i] != float('inf'):
                res = min(res, i)
        return res if res != float('inf') else -1

import bisect
from typing import List
from functools import lru_cache


class Solution:
    def makeArrayIncreasing(self, arr1: List[int], arr2: List[int]) -> int:
        array = arr1
        replace = list(sorted(set(arr2)))

        @lru_cache(None)
        def dfs(array_pos: int, prev_number: int) -> int:
            min_replacements = len(replace) * 2

            if array_pos == len(array):
                return 0

            next_replace_pos = 0

            if array_pos > 0:
                next_replace_pos = bisect.bisect(replace, array[array_pos - 1])

            if array_pos == 0 or (
                next_replace_pos < len(replace)
            ):
                tmp = array[array_pos]
                array[array_pos] = replace[next_replace_pos]
                min_replacements = min(min_replacements, dfs(array_pos + 1, array[array_pos]) + 1)
                array[array_pos] = tmp

            if array_pos == 0 or array[array_pos - 1] < array[array_pos]:
                min_replacements = min(min_replacements, dfs(array_pos + 1, array[array_pos]))

            return min_replacements

        result = dfs(0, -100)

        if result > len(replace):
            return -1

        return result


import bisect

class Solution:
    def makeArrayIncreasing(self, arr1, arr2) -> int:
        N = len(arr1)
        arr1 = [0] + arr1
        arr2.sort()
        dp = [[float('inf')] * (N + 1) for _ in range(N + 1)]
        dp[0][0] = -float('inf')
        
        for i in range(1, N + 1):
            for j in range(0, i + 1):
                if dp[i-1][j] < arr1[i]:
                    dp[i][j] = min(dp[i][j], arr1[i])
                if j >= 1:
                    # 要在 arr2 中找到一个比 arr1[i] 稍微大一点的数
                    idx_2 = bisect.bisect_right(arr2, dp[i-1][j-1])
                    if idx_2 != len(arr2):
                        dp[i][j] = min(dp[i][j], arr2[idx_2])
        
        # 满足条件，并且能够执行最少的次数的 K 的值
        res = float('inf')
        for i in range(1, N + 1):
            if dp[N][i] != float('inf'):
                res = min(res, i)
        return -1 if res == float('inf') else res

import bisect
import functools
class Solution:
    def makeArrayIncreasing(self, arr1: List[int], arr2: List[int]) -> int:
        arr2=sorted(set(arr2))
        
        @functools.lru_cache(None)
        def dfs(i,prev):
            if i>=len(arr1):
                return 0
            j=bisect.bisect_right(arr2,prev)
            swap=1+dfs(i+1,arr2[j]) if j<len(arr2) else math.inf
            noswap=dfs(i+1,arr1[i]) if arr1[i]>prev else math.inf
            return min(swap,noswap)
        
        changes=dfs(0,-math.inf)
        return changes if changes!=math.inf else -1

class Solution:
    def makeArrayIncreasing(self, arr1: List[int], arr2: List[int]) -> int:
        def bs(arr, l, r, target):
            while l<=r:
                m = l+(r-l)//2
                if arr[m]>target:
                    r = m-1
                else:
                    l = m+1
            return l
        
        arr2.sort()
        N = len(arr2)
        dp = {-1:0}
        
        for a in arr1:
            dp2 = {}
            for prev in dp:
                if a>prev:
                    dp2[a] = min(dp2.get(a, float('inf')), dp[prev])
                
                idx = bs(arr2, 0, N-1, prev)
                if idx<N:
                    dp2[arr2[idx]] = min(dp2.get(arr2[idx], float('inf')), dp[prev]+1)
                    
            dp = dp2
            if not dp:
                return -1
            
        return min(dp.values())

import bisect
from functools import lru_cache


class Solution:
    def makeArrayIncreasing(self, A: List[int], B: List[int]) -> int:
        B = sorted(set(B))
        
        def find_lower_val_in_B(val):
            larger_equal_idx = bisect.bisect_left(B, val)
            if larger_equal_idx > 0:
                return B[larger_equal_idx - 1]
            return None  # no lower value in B

        @lru_cache(None)
        def make_prefix_increasing(n, upper=float('inf')):
            if n == 0:
                return 0

            swap_b = find_lower_val_in_B(upper)
            ret = float('inf')
            if A[n - 1] < upper:
                ret = min(make_prefix_increasing(n - 1, upper=A[n - 1]), ret)
            if swap_b is not None:
                ret = min(1 + make_prefix_increasing(n - 1, upper=swap_b), ret)

            return ret

        ret = make_prefix_increasing(len(A))
        return ret if ret < float('inf') else -1


class Solution:
    def makeArrayIncreasing(self, A: List[int], B: List[int]) -> int:
        
        dp = {-1:0}
        B = sorted(B)
        
        for cur in A:
            temp = collections.defaultdict(lambda: float('inf'))
            for prev in dp:
                if prev<cur:
                    temp[cur] = min(temp[cur], dp[prev])
                idx = self.upper_bound(B, prev)
                if idx<len(B):
                    temp[B[idx]] = min(temp[B[idx]], dp[prev]+1) 
            dp = temp
        
        if dp:
            return min(dp.values())
        return -1
    
    def upper_bound(self, B, target):
        l=0
        r=len(B)
        while l<r:
            mid=l+(r-l)//2
            if B[mid]<=target:
                l=mid+1
            else:
                r=mid
        return l
                
                


import bisect
from functools import lru_cache


class Solution:
    def makeArrayIncreasing(self, A: List[int], B: List[int]) -> int:
        B = sorted(set(B))

        @lru_cache(None)
        def find_larger_value_in_B(val):
            if val >= B[-1]:
                return float('inf')
            return B[bisect.bisect_right(B, val)]

        @lru_cache(None)
        def min_last_value_given_operations(n, ops):
            if ops < 0:
                return float('inf')
            elif n == 0:
                return float('-inf')
            elif ops > n:
                return min_last_value_given_operations(n, n)
            return min(
                A[n - 1] if min_last_value_given_operations(n - 1, ops) < A[n - 1] else float('inf'),
                find_larger_value_in_B(min_last_value_given_operations(n - 1, ops - 1)),
            )

        last_success = -1
        for ops in range(min(len(A), len(B)), -1, -1):
            if min_last_value_given_operations(len(A), ops) == float('inf'):
                break
            last_success = ops

        return last_success


class Solution:
    def makeArrayIncreasing(self, arr1: List[int], arr2: List[int]) -> int:
        if not arr1: return 0
        if not arr2: return arr1 == sorted(arr1)
        
        arr2 = sorted(list(set(arr2)), reverse=True)
        
        n, m, inf = len(arr1), len(arr2), float('inf')
        f = [[inf]*(n+1) for _ in range(n)]
        for i in range(n+1):
            f[0][i] = min(arr1[0],arr2[-1])
        f[0][0] = arr1[0]
        for i in range(1,n):
            found_k = 0
            for j in range(n+1):
                if f[i-1][j] < arr1[i]: f[i][j] = arr1[i]
                if not j: continue
                va = f[i-1][j-1]
                if not found_k:
                    if arr2[0] > va:
                        l,r = 0,m-1
                        while l < r:
                            mid = l+r+1 >> 1
                            if arr2[mid] > va:
                                l = mid
                            else: 
                                r = mid - 1
                        k = l
                        found_k = 1
                        f[i][j] = min(f[i][j],arr2[k])
                else:
                    while k+1 < m and arr2[k+1] > va: k += 1
                    f[i][j] = min(f[i][j],arr2[k])
        for i,v in enumerate(f[-1]): 
            if v < inf: return i
        return -1
                
                
                


import bisect
from functools import lru_cache


class Solution:
    def makeArrayIncreasing(self, A: List[int], B: List[int]) -> int:
        B = sorted(set(B))

        @lru_cache(None)
        def find_larger_value_in_B(val):
            if val >= B[-1]:
                return float('inf')
            return B[bisect.bisect_right(B, val)]

        @lru_cache(None)
        def min_last_value_given_operations(n, ops):
            if ops < 0:
                return float('inf')
            elif n == 0:
                return float('-inf')
            elif ops > n:
                return min_last_value_given_operations(n, n)

            prev_with_op = min_last_value_given_operations(n - 1, ops - 1)
            b = find_larger_value_in_B(prev_with_op)
            # dp(n - 1, ops) <= dp(n - 1, ops - 1)
            # if dp(n - 1, ops - 1) < A[n - 1] => dp(n - 1, ops) < A[n - 1]
            if prev_with_op < A[n - 1]:
                return min(A[n - 1], b)
            elif b <= A[n - 1]:
                return b
            elif min_last_value_given_operations(n - 1, ops) < A[n - 1]:
                return A[n - 1]
            return b

        for ops in range(min(len(A), len(B)) + 1):
            if min_last_value_given_operations(len(A), ops) < float('inf'):
                return ops

        return -1


class Solution:
    def makeArrayIncreasing(self, arr1: List[int], arr2: List[int]) -> int:
        #10:04
        # arr2=list(set(arr2))
        n=len(arr1)
        arr2=list(set(arr2))
        arr2.sort()
        m=len(arr2)
        # we might need fix at point 0
        # hence we will always compare it will
        def bsearch(left,right,val):
            ans=-1
            while left<=right:
                mid=left+(right-left)//2
                if arr2[mid]>val:
                    ans=mid
                    right=mid-1
                else:
                    left=mid+1
            return ans 
        
        @lru_cache(None)
        def helper(i,j,prev):
            nonlocal n,m
            if i>=len(arr1):
                # arr1 is increasing, we have reached so far
                return 0
            else:
                ans=float('inf')
                if arr1[i]>prev:
                    # no need of replacement
                    ans=min(ans,helper(i+1,j,arr1[i]))
                    # pick any index from arr2 starting j
                idx=bsearch(j,len(arr2)-1,prev)
                if idx!=-1:
                    ans=min(ans,1+helper(i+1,idx+1,arr2[idx]))
                return ans
        ans=helper(0,0,-1)
        return -1 if ans==float('inf') else ans
                
                
        
        


def binsearch(arr,x):
    if(arr[0]>x):
        return 0
    l=0
    h=len(arr)-1
    ret=-1
    while(l<=h):
        mid=(l+h)//2
        if(arr[mid]<=x):
            l=mid+1
        elif(arr[mid]>x):
            ret=mid
            h=mid-1
    return ret
class Solution:
    def makeArrayIncreasing(self, arr1: List[int], arr2: List[int]) -> int:
        arr2.sort()
        m=len(arr2)
        n=len(arr1)
        dp={}
        # print(binsearch(arr2,0))
        def dfs(arr1,arr2,left,curr,dp):
            if(curr>=len(arr1)):
                return 0
            if((curr,left) in dp):
                return dp[(curr,left)]
            res1=sys.maxsize
            res2=0
            if(arr1[curr]>left):
                res1=dfs(arr1,arr2,arr1[curr],curr+1,dp)
            mid=binsearch(arr2,left)
            if(mid==-1):
                res2=sys.maxsize-1
            else:
                res2=dfs(arr1,arr2,arr2[mid],curr+1,dp)
            dp[(curr,left)]=min(res1,1+res2)
            return dp[(curr,left)]
        x=dfs(arr1,arr2,-sys.maxsize,0,dp)
        if(x>=(sys.maxsize-1)):
            return -1
        return x
            


def binsearch(arr,x):
    if(arr[0]>x):
        return 0
    l=0
    h=len(arr)-1
    ret=-1
    while(l<=h):
        mid=(l+h)//2
        if(arr[mid]<=x):
            l=mid+1
        elif(arr[mid]>x):
            ret=mid
            h=mid-1
    return ret
class Solution:
    def makeArrayIncreasing(self, arr1: List[int], arr2: List[int]) -> int:
        arr2.sort()
        m=len(arr2)
        n=len(arr1)
        dp={}
        def dfs(arr1,arr2,left,curr,dp):
            if(curr>=len(arr1)):
                return 0
            if((curr,left) in dp):
                return dp[(curr,left)]
            res1=sys.maxsize
            res2=0
            if(arr1[curr]>left):
                res1=dfs(arr1,arr2,arr1[curr],curr+1,dp)
            mid=binsearch(arr2,left)
            if(mid==-1):
                res2=sys.maxsize-1
            else:
                res2=dfs(arr1,arr2,arr2[mid],curr+1,dp)
            dp[(curr,left)]=min(res1,1+res2)
            return dp[(curr,left)]
        x=dfs(arr1,arr2,-sys.maxsize,0,dp)
        if(x==(sys.maxsize)):
            return -1
        return x
            


import bisect
from functools import lru_cache


class Solution:
    def makeArrayIncreasing(self, A: List[int], B: List[int]) -> int:
        B = sorted(set(B))
        b2idx = {b: i for i, b in enumerate(B)}
        
        # @lru_cache(None)
        def find_larger_value_in_B(val):
            if val >= B[-1]:
                return float('inf')
            if val in b2idx:
                return B[b2idx[val] + 1]
            return B[bisect.bisect_right(B, val)]

        @lru_cache(None)
        def min_last_value_given_operations(n, ops):
            if ops < 0:
                return float('inf')
            elif n == 0:
                return float('-inf')
            elif ops > n:
                return min_last_value_given_operations(n, n)

            skip_op = min_last_value_given_operations(n - 1, ops)
            if skip_op == float('inf'):
                return float('inf')
            return min(
                A[n - 1] if skip_op < A[n - 1] else float('inf'),
                find_larger_value_in_B(min_last_value_given_operations(n - 1, ops - 1)),
            )

        last_success = -1
        for ops in range(min(len(A), len(B)), -1, -1):
            if min_last_value_given_operations(len(A), ops) == float('inf'):
                break
            last_success = ops

        return last_success


class Solution:
    def makeArrayIncreasing(self, arr1: List[int], arr2: List[int]) -> int:
        #10:04
        # arr2=list(set(arr2))
        arr2.sort()
        # we might need fix at point 0
        # hence we will always compare it will
        
        def bsearch(left,right,val):
            ans=-1
            while left<=right:
                mid=left+(right-left)//2
                if arr2[mid]>val:
                    ans=mid
                    right=mid-1
                else:
                    left=mid+1
            return ans 
        
        @lru_cache(None)
        def helper(i,j,prev):
            if i>=len(arr1):
                # arr1 is increasing, we have reached so far
                return 0
            else:
                ans=float('inf')
                if arr1[i]>prev:
                    # no need of replacement
                    ans=min(ans,helper(i+1,j,arr1[i]))
                    # pick any index from arr2 starting j
                idx=bsearch(j,len(arr2)-1,prev)
                if idx!=-1:
                    ans=min(ans,1+helper(i+1,idx+1,arr2[idx]))
                return ans
        ans=helper(0,0,-1)
        return -1 if ans==float('inf') else ans
                
                
        
        


class Solution:
    def makeArrayIncreasing(self, arr1: List[int], arr2: List[int]) -> int:
        #10:04
        # arr2=list(set(arr2))
        n=len(arr1)
        arr2=list(set(arr2))
        arr2.sort()
        m=len(arr2)
        # we might need fix at point 0
        # hence we will always compare it will
        def bsearch(left,right,val):
            ans=-1
            while left<=right:
                mid=left+(right-left)//2
                if arr2[mid]>val:
                    ans=mid
                    right=mid-1
                else:
                    left=mid+1
            return ans 
        
        @lru_cache(None)
        def helper(i,j,prev):
            nonlocal n,m
            if i>=n:
                # arr1 is increasing, we have reached so far
                return 0
            else:
                ans=float('inf')
                if arr1[i]>prev:
                    # no need of replacement
                    ans=min(ans,helper(i+1,j,arr1[i]))
                    # pick any index from arr2 starting j
                idx=bsearch(j,m-1,prev)
                if idx!=-1:
                    ans=min(ans,1+helper(i+1,idx+1,arr2[idx]))
                return ans
        ans=helper(0,0,-1)
        return -1 if ans==float('inf') else ans
                
                
        
        


class Solution:
    def makeArrayIncreasing(self, arr1: List[int], arr2: List[int]) -> int:
        #10:04
        # arr2=list(set(arr2))
        arr2.sort()
        # we might need fix at point 0
        # hence we will always compare it will
        def bsearch(left,right,val):
            ans=-1
            while left<=right:
                mid=left+(right-left)//2
                if arr2[mid]>val:
                    ans=mid
                    right=mid-1
                else:
                    left=mid+1
            return ans
        
        @lru_cache(None)
        def helper(i,j,prev):
            if i>=len(arr1):
                # arr1 is increasing, we have reached so far
                return 0
            else:
                ans=float('inf')
                if arr1[i]>prev:
                    # no need of replacement
                    ans=min(ans,helper(i+1,j,arr1[i]))
                    # pick any index from arr2 starting j
                idx=bsearch(j,len(arr2)-1,prev)
                if idx!=-1:
                    ans=min(ans,1+helper(i+1,idx+1,arr2[idx]))
                
                    
#                 for k in range(j,len(arr2)):
#                     # can we use binary search here
#                     # we got to find out the minumum value in arr2 which is greater than prev
                    
#                     if arr2[k]>prev:
#                         # we can probably use binary search here
#                         # get the first index which is strictly greater than prev
#                         ans=min(ans,1+helper(i+1,k+1,arr2[k]))
#                         break
                return ans
        ans=helper(0,0,-1)
        return -1 if ans==float('inf') else ans
                
                
        
        


import bisect
class Solution:
    def recurse(self,arr1,arr2,m,n,idx,prev,dp):
        if idx>=n:
            return 0
        k=bisect.bisect_right(arr2,prev)
        if dp[idx][k]!=-1:
            return dp[idx][k]
        c1=self.recurse(arr1,arr2,m,n,idx+1,arr1[idx],dp) if arr1[idx]>prev else 2000
        c2=1+self.recurse(arr1,arr2,m,n,idx+1,arr2[k],dp) if k<m else 2000
        dp[idx][k]=min(c1,c2)
        return dp[idx][k]
     

    def makeArrayIncreasing(self, arr1: List[int], arr2: List[int]) -> int:
        dp=[[-1 for i in range(2001)] for j in range(2001)]
        arr2.sort()
        self.recurse(arr1,arr2,len(arr2),len(arr1),0,-10**9,dp)
        if dp[0][0]>=2000:
            return -1
        else:
            return dp[0][0]
      


class Solution:
    def makeArrayIncreasing(self, arr1: List[int], arr2: List[int]) -> int:
        # Maintain two dp array: 1 for keep arr1[i], 1 for swap arr1[i] with arr2[j]
        # Convert arr2 to sorted unique set
        a = arr1
        b = sorted(list(set(arr2)))
        n, m = len(a), len(b)
        keep = [0, math.inf]  # keep[i] = keep a[i]
        swap = [[1] * m, [math.inf] * m]  # swap[i][j] = a[i] replaced with b[j]

        prev, curr = 1, 0
        for i in range(1, n):
            prev, curr = curr, prev
            # must init every time
            swap[curr] = [math.inf] * m
            keep[curr] = math.inf
            # keep[i] case 1: a[i] is bigger than previous keep[i-1]
            if a[i] > a[i - 1]:
                keep[curr] = keep[prev]
            for j in range(m):
                # keep[i] case 2: a[i] is bigger then previous swap value.
                if a[i] > b[j]:
                    keep[curr] = min(keep[curr], swap[prev][j])
                # swap case 1: when a[i-1] keeps
                if b[j] > a[i - 1]:
                    swap[curr][j] = min(swap[curr][j], 1 + keep[prev])
                # Swap case 2: when a[i-1] swapped
                if j > 0:
                    # only need to check last swap[i-1][j-1] since swap[][j] decreases when j increases.
                    swap[curr][j] = min(swap[curr][j], 1 + swap[prev][j - 1])

        res = min(keep[curr], swap[curr][m - 1])
        return res if res < math.inf else -1

class Solution:
    def makeArrayIncreasing(self, arr1: List[int], arr2: List[int]) -> int:
        #10:04
        # arr2=list(set(arr2))
        n=len(arr1)
        arr2=list(set(arr2))
        arr2.sort()
        m=len(arr2)
        # we might need fix at point 0
        # hence we will always compare it will
        def bsearch(left,right,val):
            ans=-1
            while left<=right:
                mid=left+(right-left)//2
                if arr2[mid]>val:
                    ans=mid
                    right=mid-1
                else:
                    left=mid+1
            return ans 
        
        @lru_cache(None)
        def helper(i,j,prev):
            nonlocal n,m
            if i>=n:
                # arr1 is increasing, we have reached so far
                return 0
            else:
                ans=float('inf')
                if arr1[i]>prev:
                    # no need of replacement
                    ans=min(ans,helper(i+1,j,arr1[i]))
                # pick first index from arr2 starting j which is greater than prev
                idx=bsearch(j,m-1,prev)
                if idx!=-1:
                    ans=min(ans,1+helper(i+1,idx+1,arr2[idx]))
                return ans
        ans=helper(0,0,-1)
        return -1 if ans==float('inf') else ans

    
                
                
        
        


import bisect
class Solution:
    def recurse(self,arr1,arr2,m,n,idx,prev,dp):
        if idx>=n:
            return 0
        k=bisect.bisect_right(arr2,prev)
        if dp[idx][k]!=-1:
            return dp[idx][k]
        c1=self.recurse(arr1,arr2,m,n,idx+1,arr1[idx],dp) if arr1[idx]>prev else 2000
        c2=1+self.recurse(arr1,arr2,m,n,idx+1,arr2[k],dp) if k<m else 2000
        dp[idx][k]=min(c1,c2)
        return dp[idx][k]
     

    def makeArrayIncreasing(self, arr1: List[int], arr2: List[int]) -> int:
        dp=[[-1 for i in range(2001)] for j in range(2001)]
        arr2.sort()
        ans=self.recurse(arr1,arr2,len(arr2),len(arr1),0,-10**9,dp)
        if ans>=2000:
            return -1
        else:
            return ans
      


class Solution:
    def makeArrayIncreasing(self, arr1: List[int], arr2: List[int]) -> int:
        # Maintain two dp array: 1 for keep arr1[i], 1 for swap arr1[i] with arr2[j]
        # Convert arr2 to sorted unique set
        a = arr1
        b = sorted(list(set(arr2)))
        n, m = len(a), len(b)
        keep = [math.inf] * n  # keep[i] = keep a[i]
        swap = [[math.inf] * m for _ in range(n)]  # swap[i][j] = a[i] replaced with b[j]
        # init
        keep[0] = 0  # keep a[0], no swap
        swap[0] = [1] * m  # can be swapped with any a[j]

        for i in range(1, n):
            # keep[i] case 1: a[i] is bigger than previous keep[i-1]
            if a[i] > a[i - 1]:
                keep[i] = keep[i - 1]
            for j in range(m):
                # keep[i] case 2: a[i] is bigger then previous swap value.
                if a[i] > b[j]:
                    keep[i] = min(keep[i], swap[i - 1][j])
                # swap case 1: when a[i-1] keeps
                if b[j] > a[i - 1]:
                    swap[i][j] = min(swap[i][j], 1 + keep[i - 1])
                # Swap case 2: when a[i-1] swapped
                if j > 0:
                    # only need to check last swap[i-1][j-1] since swap[][j] decreases when j increases.
                    swap[i][j] = min(swap[i][j], 1 + swap[i - 1][j - 1])

        res = min(keep[n - 1], swap[n - 1][m - 1])
        return res if res < math.inf else -1        

class Solution:
    def makeArrayIncreasing(self, arr1: List[int], arr2: List[int]) -> int:
        arr2.sort()
        m = len(arr1)
        n = len(arr2)
        newarr2 = [arr2[0]]
        for i in range(1, n):
            if arr2[i] != newarr2[-1]:
                newarr2.append(arr2[i])
                
        arr2 = newarr2
        n = len(arr2)

        IL = 10 ** 9 + 7
        
        dp = [[IL for j in range(n + 1)] for i in range(m)]
        
        dp[0][n] = 0
        for i in range(n):
            if arr2[i] < arr1[0]:
                dp[0][i] = 1
            else:
                break
        
        for i in range(1, m):
            idx = 0
            if arr2[0] > arr1[i - 1]:
                dp[i][0] = dp[i - 1][n] + 1
            
            for k in range(1, n):
                a = dp[i - 1][n] + 1 if dp[i - 1][n] != IL and arr1[i - 1] < arr2[k] else IL
                b = dp[i - 1][idx] + 1 if dp[i - 1][idx] != IL else IL
                dp[i][k] = min(a, b)
                if dp[i - 1][k] < dp[i - 1][idx]:
                    idx = k
                    
            if dp[i - 1][n] != IL and arr1[i] > arr1[i -1]:
                dp[i][n] = dp[i - 1][n]
            
            for k in range(n):
                if dp[i - 1][k] != IL and arr2[k] < arr1[i]:
                    dp[i][n] = min(dp[i][n], dp[i - 1][k])
                    
        m = min(dp[m - 1])
        
        return m if m != IL else -1
        
                


class Solution:    
    def binary_search_right(self, arr, l, r, t):
        while l < r:
            m = l + (r - l) // 2
            if arr[m] <= t:
                l = m + 1
            else:
                r = m
        return l
    
    def makeArrayIncreasing(self, arr1: List[int], arr2: List[int]) -> int:
        arr2.sort()
        
        dp = {}
        def help(i1, i2):
            if i1 == len(arr1):
                return 0
            
            if i1 != 0:
                key = (i1, i2, arr1[i1 - 1])
            else:
                key = (i1, i2, None)
            
            if key in dp:
                return dp[key]
            
            # print(key)
            
            # all possible results
            pos = []
            
            # don't make changes here
            if i1 == 0 or arr1[i1 - 1] < arr1[i1]:
                res = help(i1 + 1, i2)
                if res != -1:
                    pos.append(res)
                    
            if i1 != 0:
                # make change
                i2 = self.binary_search_right(arr2, i2, len(arr2), arr1[i1 - 1])
                if i2 != len(arr2):
                    tmp = arr1[i1]
                    arr1[i1] = arr2[i2]
                    res = help(i1 + 1, i2 + 1)
                    if res != -1:
                        pos.append(res + 1)
                    arr1[i1] = tmp
            else:
                # make change
                if i2 < len(arr2) and arr2[i2] < arr1[i1]:
                    tmp = arr1[i1]
                    arr1[i1] = arr2[i2]
                    res = help(i1 + 1, i2 + 1)
                    if res != -1:
                        pos.append(res + 1)
                    arr1[i1] = tmp
            
            if len(pos) == 0:
                dp[key] = -1
            else:
                dp[key] = min(pos)
            return dp[key]
        
        return help(0, 0)

class Solution:
    def makeArrayIncreasing(self, arr1: List[int], arr2: List[int]) -> int:
        n = len(arr1)
        arr1.insert(0, -1)
        arr2.sort()
        
        # dp[i][k] means the minimum number we can have at ith position with k operations
        dp = [[sys.maxsize for k in range(n + 1)] for i in range(n + 1)]
        dp[0][0] = -1
        
        for i in range(1, n + 1):
            for k in range(i + 1):
                if dp[i - 1][k] < arr1[i]:
                    # not assign
                    dp[i][k] = arr1[i]
                
                num = self.helper(arr2, dp[i - 1][k - 1])
                if num > dp[i - 1][k - 1]:
                    dp[i][k] = min(dp[i][k], num)
        
        ans = sys.maxsize
        for k in range(n + 1):
            if dp[n][k] < sys.maxsize:
                ans = min(ans, k)
        return ans if ans < sys.maxsize else -1

    def helper(self, arr, val):
        # find in arr the smallest number that is larger than val
        start, end = 0, len(arr) - 1
        while start + 1 < end:
            mid = start + (end - start) // 2
            if arr[mid] <= val:
                start = mid
            else:
                end = mid
        
        if arr[start] > val:
            return arr[start]
        return arr[end]

class Solution:
    def makeArrayIncreasing(self, arr1: List[int], arr2: List[int]) -> int:
        arr2 = sorted(set(arr2))
        size1, size2 = len(arr1), len(arr2)
        Inf = float('inf')
        keep = [Inf] * size1
        keep[0] = 0
        swap = [[Inf] * size2 for _ in range(size1)]
        swap[0] = [1] * size2
        for i in range(1, size1):
            minKeep = minSwap = Inf
            for j in range(size2):
                if arr1[i] > arr1[i-1]:
                    keep[i] = keep[i-1]
                if arr1[i] > arr2[j]:
                    minKeep = min(minKeep, swap[i-1][j])
                if arr2[j] > arr1[i-1]:
                    swap[i][j] = keep[i-1] + 1
                if j > 0: # arr2[j] > arr2[j-1] is always True
                    minSwap = min(minSwap, swap[i-1][j-1] + 1)
                keep[i] = min(keep[i], minKeep)
                swap[i][j] = min(swap[i][j], minSwap)
        res = min(min(swap[-1]), keep[-1])
        return -1 if res == Inf else res


class Solution:
    def makeArrayIncreasing(self, arr1: List[int], arr2: List[int]) -> int:
        n = len(arr1)
        arr1.insert(0, -1)
        arr2.sort()
        
        # dp[i][k] means the minimum number we can have at ith position with k operations
        dp = [[sys.maxsize for k in range(n + 1)] for i in range(n + 1)]
        dp[0][0] = -1
        
        for i in range(1, n + 1):
            for k in range(i + 1):
                if dp[i - 1][k] < arr1[i]:
                    # not assign
                    dp[i][k] = arr1[i]
                
                if k >= 1:
                    num = self.helper(arr2, dp[i - 1][k - 1])
                    if num > dp[i - 1][k - 1]:
                        dp[i][k] = min(dp[i][k], num)
        
        ans = sys.maxsize
        for k in range(n + 1):
            if dp[n][k] < sys.maxsize:
                ans = min(ans, k)
        return ans if ans < sys.maxsize else -1

    def helper(self, arr, val):
        # find in arr the smallest number that is larger than val
        start, end = 0, len(arr) - 1
        while start + 1 < end:
            mid = start + (end - start) // 2
            if arr[mid] <= val:
                start = mid
            else:
                end = mid
        
        if arr[start] > val:
            return arr[start]
        return arr[end]

class Solution:
    def makeArrayIncreasing(self, arr1: List[int], arr2: List[int]) -> int:
        n = len(arr1)
        arr1.insert(0, -1)
        arr2.sort()
        # dp[i][k] means the minimum number we can get at arr1[i] using k operations
        dp = [[sys.maxsize for k in range(n + 1)] for i in range(n + 1)]
        dp[0][0] = -1
        
        for i in range(1, n + 1):
            for k in range(i + 1):
                # not changing for arr1[i]
                if dp[i - 1][k] < arr1[i]:
                    dp[i][k] = arr1[i]
                
                # changing for arr1[i]
                # find the smallested number in arr2 that is larger than dp[i - 1][k - 1]
                if k >= 1:
                    num = self.helper(arr2, dp[i - 1][k - 1])
                    if num > dp[i - 1][k - 1]:
                        dp[i][k] = min(dp[i][k], num)
        
        ans = sys.maxsize
        for k in range(0, n + 1):
            if dp[n][k] < sys.maxsize:
                ans = min(ans, k)
        return ans if ans < sys.maxsize else -1
    
    def helper(self, arr, val):
        start, end = 0, len(arr) - 1
        while start + 1 < end:
            mid = start + (end - start) // 2
            if arr[mid] <= val:
                start = mid
            elif arr[mid] > val:
                end = mid
        
        if arr[start] > val:
            return arr[start]
        return arr[end]

class Solution:
    def makeArrayIncreasing(self, arr1: List[int], arr2: List[int]) -> int:
        set2 = set(arr2)
        arr2 = sorted(set2)
        N, M = len(arr1), len(arr2)
        to_index = {}
        left = 0
        for x in sorted(arr1):
            while left < M and arr2[left] <= x:
                left += 1
            to_index[x] = left - 1 if left < M else M
        
        print(to_index, arr2)
        dp = [[[None, None] for _ in range(M + 1)] for _ in range(N)]
        
        def solve(i, j, k):
            if i == N: return 0
            if j > M or (j == M and k == 1): return N+1
            if dp[i][j][k] is None:
                if i == 0: 
                    dp[i][j][k] = min(solve(i+1, to_index[arr1[0]], 0), 1 + solve(i+1, 0, 1))
                else:
                    result = N + 1
                    if j < M - 1: 
                        result = 1 + solve(i+1, j+1, 1)
                    if k == 0 and arr1[i] > arr1[i-1]:
                        result = min(result, solve(i+1, to_index[arr1[i]], 0))
                    if k == 1 and arr1[i] > arr2[j]:
                        result = min(result, solve(i+1, to_index[arr1[i]], 0))
                    dp[i][j][k] = result
            return dp[i][j][k]
        result = solve(0, 0, 0)
        # for i in range(N):
        #     for j in range(M):
        #         for k in [0, 1]:
        #             print(dp[i][j][k], i, j, k)
        return result if result <= N else -1

import bisect
from functools import lru_cache


class Solution:
    def makeArrayIncreasing(self, A: List[int], B: List[int]) -> int:
        B = sorted(set(B))

        def find_larger_value_in_B(val):
            if val >= B[-1]:
                return float('inf')
            return B[bisect.bisect_right(B, val)]

        @lru_cache(None)
        def min_last_value_given_operations(n, ops):
            if ops < 0:
                return float('inf')
            if n == 0:
                return float('-inf')
                # return A[n - 1] if first_n_of_A_is_sorted(n) else float('inf')

            ops = min(n, ops)
            return min(
                A[n - 1] if min_last_value_given_operations(n - 1, ops) < A[n - 1] else float('inf'),
                find_larger_value_in_B(min_last_value_given_operations(n - 1, ops - 1)),
            )

        for ops in range(min(len(A), len(B)) + 1):
            if min_last_value_given_operations(len(A), ops) < float('inf'):
                return ops

        return -1


class Solution:
    def makeArrayIncreasing(self, arr1: List[int], arr2: List[int]) -> int:
        ## https://www.youtube.com/watch?v=8ttxdMCU2GE
        m = len(arr1)
        ## remove dulpicates and sort arr2
        arr2 = sorted(list(set(arr2)))
        # print(arr2)
        n = len(arr2)
        swap = [[float('inf') for j in range(n)] for i in range(m)]
        keep = [float('inf') for i in range(m)]
        
        ## initialization
        keep[0] = 0
        for j in range(n):
            swap[0][j] = 1
            
        for i in range(1, m):
            min_keep = float('inf')
            min_swap = float('inf')
            for j in range(n):
                ## two variables to help compute case 3 & 4
                ## case 4: the last two elements of current valid array are both from arr2
                if j>0:
                    min_swap = min(min_swap, swap[i-1][j-1]+1)

                ## case 3: the second to last element is replaced by the previous element arr2[j-1] or earlier elements
                if arr1[i]>arr2[j]:
                    min_keep = min(min_keep, swap[i-1][j])
                    
                ## case 1: no need to swap; keep arr1[i]
                if arr1[i]>arr1[i-1]:
                    keep[i] = keep[i-1]
                
                ## case 2: ## replace arr1[i] by arr2[j]
                if arr2[j]>arr1[i-1]:
                    swap[i][j] = keep[i-1] + 1
                
                ## update
                swap[i][j] = min(swap[i][j], min_swap)
                keep[i] = min(keep[i], min_keep)
                
        # for i in range(m):
        #     print(keep[i], swap[i])
                
        res = min(min(swap[m-1]), keep[m-1])
        if res == float('inf'):
            return -1
        else:
            return res