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: MEDIUM
Tags: Dynamic programming

Sorting

Data structures
Skill types: Dynamic programming

Sorting

Data structures

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)
			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}
		for n1 in arr1:
			new_dp = {}
			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
			dp = new_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


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


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


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


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(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:
		(m, n) = (len(arr1), len(arr2))
		arr2.sort()
		ss = [(0, arr1[0], 0)]
		if arr2[0] < arr1[0]:
			ss.append((1, arr2[0], 1))
		for i in range(1, m):
			st = []
			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))
				while j < n and arr2[j] <= x:
					j += 1
				if j < n:
					st.append((s + 1, arr2[j], j))
			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

class Solution:

	def makeArrayIncreasing(self, arr1: List[int], arr2: List[int]) -> int:
		N = len(arr1)
		arr1 = [0] + arr1
		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):
				if arr1[i] > dp[i - 1][k]:
					dp[i][k] = min(dp[i][k], arr1[i])
				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


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

		@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


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


class Solution:

	def makeArrayIncreasing(self, arr1: List[int], arr2: List[int]) -> int:
		n = len(arr1)
		arr2 = list(set(arr2))
		arr2.sort()
		m = len(arr2)

		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):
				return 0
			else:
				ans = float('inf')
				if arr1[i] > prev:
					ans = min(ans, helper(i + 1, j, arr1[i]))
				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 = {}

		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


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:
		a = arr1
		b = sorted(list(set(arr2)))
		(n, m) = (len(a), len(b))
		keep = [0, math.inf]
		swap = [[1] * m, [math.inf] * m]
		(prev, curr) = (1, 0)
		for i in range(1, n):
			(prev, curr) = (curr, prev)
			swap[curr] = [math.inf] * m
			keep[curr] = math.inf
			if a[i] > a[i - 1]:
				keep[curr] = keep[prev]
			for j in range(m):
				if a[i] > b[j]:
					keep[curr] = min(keep[curr], swap[prev][j])
				if b[j] > a[i - 1]:
					swap[curr][j] = min(swap[curr][j], 1 + keep[prev])
				if j > 0:
					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:
		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]
			pos = []
			if i1 == 0 or arr1[i1 - 1] < arr1[i1]:
				res = help(i1 + 1, i2)
				if res != -1:
					pos.append(res)
			if i1 != 0:
				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
			elif 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 = [[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]:
					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):
		(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:
					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:
		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)
		return result if result <= N else -1