Read problems statements in Mandarin chinese, Russian and Vietnamese as well. 

Daniil is a royal gardener. He takes care of a garden with $N$ plants numbered $1$ through $N$. For each $i$ ($1 ≤ i ≤ N$), the initial height of the $i$-th plant is $A_{i}$. Unfortunately, the Queen doesn't like the garden, so she asked Daniil to cut some plants — in order to satisfy the Queen's request, the $i$-th plant should have height $B_{i}$ (for each $1 ≤ i ≤ N$).

Daniil is allowed to perform the following operation an arbitrary number of times (including zero):
Let's denote the current heights of plants by $H_{1}, H_{2}, \dots, H_{N}$.
Choose two indices $L$ and $R$ ($1 ≤ L ≤ R ≤ N$) and a new height $h$ such that $h ≤ H_{i}$ for each $i$ between $L$ and $R$ inclusive.
Cut plants $L$ through $R$ down to height $h$, i.e. change the height of plant $i$ to $h$ for each $L ≤ i ≤ R$.

Some time ago, Daniil was one of the best competitive programmers. Therefore, he is interested in the minimum number of operations needed to satisfy the Queen's request. Can you help him?

------  Input ------
The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
The first line of each test case contains a single integer $N$ denoting the number of plants.
The second line contains $N$ space-separated integers $A_{1}, A_{2}, \dots, A_{N}$ denoting the initial heights of plants.
The third line contains $N$ space-separated integers $B_{1}, B_{2}, \dots, B_{N}$ denoting the final heights of plants.

------  Output ------
For each test case, print a single line containing one integer — the minimum number of operations needed to obtain the desired sequence of heights or $-1$ if it is impossible.

------  Constraints ------
$1 ≤ T ≤ 10$
$1 ≤ N ≤ 10^{5}$
$1 ≤ A_{i}, B_{i} ≤ 10^{9}$ for each valid $i$

------  Subtasks ------
Subtask #1 (30 points): 
$1 ≤ N ≤ 1,000$
the initial heights of all plants are identical

Subtask #2 (30 points): $1 ≤ N ≤ 1,000$

Subtask #3 (40 points): original constraints

----- Sample Input 1 ------ 
4
3
3 1 3
2 1 2
7
1 3 4 5 1 2 3
1 2 1 2 1 1 1
3
2 3 9
2 3 9
2
1 2
2 1
----- Sample Output 1 ------ 
2
3
0
-1
----- explanation 1 ------ 
Example case 1:
Daniil can perform two operations: reduce the height of the first plant to $2$ and reduce the height of the third plant to $2$. Note that it is not possible to reduce the heights of all three plants to $2$ in one operation, because the second plant's height is less than $2$. We need two operations, thus the answer is $2$.

Example case 2:
In the first operation, cut the plants in the interval $[2, 4]$ down to height $2$. Afterwards, cut the third plant down to height $1$. Finally, cut the plants in the interval $[6, 7]$.

Example case 3:
All plants already have the desired heights, so the answer is $0$.

Example case 4:
It is impossible to achieve the desired sequence of heights.

Source: codechef | Difficulty: HARD
Tags: Square root algorithms

Sorting

Range queries

Segment trees revisited

Data structures


Solutions:
import collections

def ii():
	return int(input())

def mi():
	return map(int, input().split())

def li():
	return list(map(int, input().split()))
for i in range(ii()):
	n = ii()
	A = li()
	B = li()
	temp = 1
	for i in range(n):
		if A[i] < B[i]:
			temp = 0
	if temp == 0:
		print(-1)
	else:
		D = collections.deque([])
		ans = 0
		for i in range(n):
			while D and D[-1] < B[i]:
				D.pop()
			while D and D[0] > A[i]:
				D.popleft()
			if A[i] != B[i]:
				if len(D) == 0:
					ans += 1
					D.append(B[i])
				elif B[i] != D[-1]:
					ans += 1
					D.append(B[i])
		print(ans)


import collections
debug = False
T = int(input())
for i in range(T):
	N = int(input())
	A = [int(x) for x in input().split()]
	B = [int(x) for x in input().split()]
	if debug:
		print('A', A)
		print('B', B)
	isPossible = True
	ans = 0
	q = collections.deque()
	for i in range(len(A)):
		if A[i] < B[i]:
			isPossible = False
	if isPossible:
		for i in range(len(A)):
			while len(q) > 0 and q[-1] < B[i]:
				q.pop()
			while len(q) > 0 and q[0] > A[i]:
				q.popleft()
			if A[i] != B[i] and (len(q) == 0 or B[i] != q[-1]):
				ans += 1
				q.append(B[i])
		print(ans)
	else:
		print(-1)


T = int(input())
for _ in range(T):
	N = int(input())
	A = [int(c) for c in input().strip().split()]
	B = [int(c) for c in input().strip().split()]
	H = A[:]
	diff = sum(A) - sum(B)
	for i in range(len(A)):
		if B[i] > A[i]:
			op = -1
			break
	else:
		op = 0
	if op == -1:
		print(-1)
		continue
	queue = []
	i = 0
	while i < len(H):
		if H[i] - B[i] > 0:
			break
		i += 1
	while i < len(H):
		while len(queue) != 0:
			if A[i] < queue[0]:
				queue.pop(0)
			else:
				break
		while len(queue) != 0:
			if B[i] > queue[-1]:
				queue.pop()
			else:
				break
		if len(queue) == 0 or queue[-1] != B[i]:
			if H[i] != B[i]:
				queue.append(B[i])
				op += 1
		i += 1
	print(op)


from collections import deque
for x in range(int(input())):
	n = int(input())
	count = 0
	a = [int(i) for i in input().split()]
	b = [int(i) for i in input().split()]
	q = deque()
	for i in range(n):
		if a[i] < b[i]:
			count = -1
	if count == 0:
		for i in range(n):
			while q and b[i] > q[-1]:
				q.pop()
			while q and a[i] < q[0]:
				q.popleft()
			if a[i] != b[i] and (not q or b[i] != q[-1]):
				count += 1
				q.append(b[i])
	print(count)


for t in range(int(input())):
	n = int(input())
	a = [int(i) for i in input().split()]
	b = [int(i) for i in input().split()]
	impossible = False
	cutting = []
	r = 0
	for i in range(n):
		if a[i] < b[i]:
			impossible = True
			print(-1)
			break
		while cutting and cutting[-1] < b[i]:
			cutting.pop()
			r += 1
		while cutting and cutting[0] > a[i]:
			cutting.pop(0)
			r += 1
		if a[i] > b[i] and (not cutting or not cutting[-1] == b[i]):
			cutting.append(b[i])
	if not impossible:
		r += len(cutting)
		print(r)


from collections import deque
for _ in range(int(input())):
	n = int(input())
	A = list(map(int, input().split()))
	B = list(map(int, input().split()))
	flag = 0
	for i in range(n):
		if B[i] > A[i]:
			print('-1')
			flag = 1
			break
	if flag == 0:
		count = 0
		t = deque()
		for i in range(n):
			while t and t[0] > A[i]:
				t.popleft()
			while t and t[-1] < B[i]:
				t.pop()
			if not t and A[i] != B[i]:
				t.append(B[i])
				count += 1
			elif t and t[-1] != B[i] and (A[i] != B[i]):
				t.append(B[i])
				count += 1
		print(count)


from collections import deque
T = int(input())
for test_case in range(T):
	n = int(input())
	init = list(map(int, input().split()))
	req = list(map(int, input().split()))
	ans = 0
	dq = deque()
	x = 0
	for i in range(0, n):
		if init[i] < req[i]:
			x = -1
	if x != -1:
		for i in range(0, n):
			while dq and dq[0] > init[i]:
				dq.popleft()
			while dq and dq[-1] < req[i]:
				dq.pop()
			if init[i] != req[i] and (not dq or dq[-1] != req[i]):
				ans = ans + 1
				dq.append(req[i])
		print(ans)
	else:
		print('-1')


from collections import deque

def solve(plant_count, init_heights, target_heights):
	answer = 0
	cuts = deque()
	for i in range(plant_count):
		if init_heights[i] < target_heights[i]:
			return -1
		while cuts and cuts[-1] < target_heights[i]:
			cuts.pop()
		while cuts and cuts[0] > init_heights[i]:
			cuts.popleft()
		if init_heights[i] > target_heights[i]:
			if not cuts:
				answer += 1
				cuts.append(target_heights[i])
			elif cuts[-1] != target_heights[i]:
				answer += 1
				cuts.append(target_heights[i])
	return answer

def solve0(plant_count, init_heights, target_heights):
	cuts = 0
	for i in range(plant_count):
		if init_heights[i] < target_heights[i]:
			return -1
		if init_heights[i] <= target_heights[i]:
			continue
		cuts += 1
		cut_height = target_heights[i]
		for j in range(i, plant_count):
			if init_heights[j] < cut_height or target_heights[j] > cut_height:
				break
			init_heights[j] = cut_height
	return cuts

def main():
	import sys
	sys.setrecursionlimit(1000000)
	test_cases = int(sys.stdin.readline())
	for _ in range(test_cases):
		plant_count = int(sys.stdin.readline())
		init_heights = [int(i) for i in sys.stdin.readline().split()]
		target_heights = [int(i) for i in sys.stdin.readline().split()]
		print(solve(plant_count, init_heights, target_heights))
main()


from collections import deque
for _ in range(int(input())):
	n = int(input())
	q = deque()
	ans = 0
	init = list(map(int, input().split()))
	final = list(map(int, input().split()))
	for i in range(n):
		if init[i] < final[i]:
			ans = -1
			break
	if ans == -1:
		print(ans)
	else:
		cnt = 0
		for i in range(n):
			while q and q[0] > init[i]:
				q.popleft()
				cnt += 1
			while q and q[-1] < final[i]:
				q.pop()
				cnt += 1
			if q:
				if final[i] != init[i] and final[i] != q[-1]:
					q.append(final[i])
			elif final[i] != init[i]:
				q.append(final[i])
		print(len(q) + cnt)


from collections import defaultdict as dd, deque
t = int(input())
inf = 10 ** 15

class Segment:

	def __init__(S, n):
		sz = 1
		while sz < n:
			sz <<= 1
		S.data = [0] * (n + sz)
		S.sz = sz

	def sum(S, l, r):
		sz = S.sz
		data = S.data
		S = 0
		l += sz
		r += sz
		while l < r:
			if l % 2 == 1:
				S += data[l]
				l += 1
			if r % 2 == 1:
				r -= 1
				S += data[r]
			l >>= 1
			r >>= 1
		return S

	def inc(S, pos):
		pos += S.sz
		while pos > 0:
			S.data[pos] += 1
			pos >>= 1

class MinSegment:

	def __init__(S, n):
		sz = 1
		while sz < n:
			sz <<= 1
		S.data = [inf] * (n + sz)
		S.sz = sz

	def min(S, l, r):
		sz = S.sz
		data = S.data
		mini = inf
		l += sz
		r += sz
		while l < r:
			if l % 2 == 1:
				mini = min(mini, data[l])
				l += 1
			if r % 2 == 1:
				r -= 1
				mini = min(mini, data[r])
			l >>= 1
			r >>= 1
		return mini

	def set(S, pos, value):
		pos += S.sz
		data = S.data
		if data[pos] > value:
			while pos > 0 and data[pos] > value:
				data[pos] = value
				pos >>= 1
		elif data[pos] < value:
			data[pos] = value
			pos >>= 1
			while pos > 0:
				data[pos] = min(data[pos * 2], data[pos * 2 + 1])
				pos >>= 1

def solve():
	n = int(input())
	A = [int(x) for x in input().split()]
	B = [int(x) for x in input().split()]
	for i in range(n):
		if B[i] > A[i]:
			return -1
	D = dd(list)
	for i in range(n):
		D[B[i]].append(i)
	locked = Segment(n)
	mini = MinSegment(n)
	for i in range(n):
		mini.set(i, A[i])
	D = sorted(D.items(), reverse=True)
	cnt = 0
	for (v, I) in D:
		i = 0
		while i < len(I):
			a = I[i]
			locked.inc(a)
			if A[a] > v:
				A[a] = v
				cnt += 1
				while i + 1 < len(I):
					b = I[i + 1]
					if locked.sum(a + 1, b) == 0 and v <= mini.min(a + 1, b):
						locked.inc(b)
						i += 1
						a = I[i]
					else:
						break
			i += 1
	return cnt
for _ in range(t):
	print(solve())


for t in range(int(input())):
	N = int(input())
	A = [int(x) for x in input().split()]
	B = [int(x) for x in input().split()]
	(cut, stack, prevh, maxheight) = (0, [], B[0], A[0])
	for x in range(N):
		if A[x] < B[x]:
			print(-1)
			break
		if maxheight > A[x]:
			cut += len(stack)
			stack = [y for y in stack if y <= A[x]]
			cut -= len(stack)
		if B[x] > prevh:
			while stack != []:
				if stack[-1] < B[x]:
					stack.pop()
					cut += 1
				else:
					break
		if B[x] < A[x]:
			if stack == []:
				stack.append(B[x])
			elif stack[-1] != B[x]:
				stack.append(B[x])
		(maxheight, prevh) = (A[x], B[x])
	else:
		cut += len(stack)
		print(cut)


def take2(elem):
	return elem[0]

def fun(i, n):
	order = [0] * n
	for i in range(n):
		order[i] = [0] * 2
		order[i][0] = brr[i]
		order[i][1] = int(i)
	order = sorted(order, key=take2)
	status = [0] * n
	(flag, tot) = (0, 0)
	for i in range(n - 1, -1, -1):
		j = order[i][1]
		if c[j] < brr[j]:
			flag = 1
			tot = -1
			break
		if status[j] == 0 and c[j] != brr[j]:
			if c[j] > brr[j]:
				c[j] = brr[j]
				tot += 1
				status[j] = 1
			for k in range(j - 1, -1, -1):
				if c[k] >= brr[j] and brr[k] <= brr[j]:
					c[k] = brr[j]
				else:
					break
				if c[k] == brr[k]:
					status[k] = 1
	return tot

def calculate(i, n):
	stack = []
	ref = []
	cut = 0
	ht = 0
	(i, flag, inc, count) = (0, 0, 0, 0)
	while i < n:
		if arr[i] < brr[i]:
			flag = 1
			break
		elif arr[i] > brr[i]:
			stack.append(brr[i])
			ref.append(arr[i])
			cut = brr[i]
			count += 1
			i += 1
			while i < n:
				same = 0
				if arr[i] == brr[i]:
					same = 1
				if arr[i] < brr[i]:
					flag = 1
					break
				if len(stack) == 0:
					if arr[i] != brr[i]:
						cut = brr[i]
						stack.append(brr[i])
						ref.append(arr[i])
						count += 1
				elif cut <= brr[i]:
					cut = brr[i]
					while len(stack) != 0 and stack[len(stack) - 1] <= brr[i]:
						if brr[i] > ref[len(stack) - 1]:
							stack = []
							ref = []
							if same == 0:
								stack.append(brr[i])
								ref.append(arr[i])
								count += 1
							break
						if brr[i] == stack[len(stack) - 1]:
							if arr[i] < ref[len(stack) - 1]:
								ref[len(stack) - 1] = arr[i]
								if len(stack) > 1:
									if stack[len(stack) - 2] > arr[i]:
										stack = []
										ref = []
										stack.append(brr[i])
										ref.append(arr[i])
								inc = 1
							break
						stack.pop()
						if arr[i] == brr[i]:
							ref.pop()
						else:
							arr[i] = min(ref.pop(), arr[i])
					if len(stack) == 0:
						if same == 0:
							stack.append(brr[i])
							ref.append(arr[i])
							if inc == 0:
								count += 1
					elif brr[i] < stack[len(stack) - 1]:
						if arr[i] < stack[len(stack) - 1]:
							stack = []
							ref = []
						if same == 0:
							stack.append(brr[i])
							ref.append(arr[i])
							if inc == 0:
								count += 1
					inc = 0
				elif arr[i] < cut:
					stack = []
					ref = []
					if arr[i] != brr[i]:
						cut = brr[i]
						stack.append(brr[i])
						ref.append(arr[i])
						count += 1
				else:
					cut = brr[i]
					stack.append(brr[i])
					ref.append(arr[i])
					count += 1
				i += 1
		i += 1
	if flag == 1:
		return -1
	else:
		return count
t = int(input())
for l in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	brr = list(map(int, input().split()))
	print(calculate(0, n))


T = int(input())
for test_case in range(T):
	N = int(input())
	I = list(map(int, input().split()))
	F = list(map(int, input().split()))
	ans = N
	chk = list()
	for (i, f) in list(zip(I, F)):
		if f > i:
			ans = -1
			break
		while len(chk) > 0 and f > chk[-1][1]:
			del chk[-1]
		if len(chk) == 0:
			if i == f:
				ans -= 1
			chk.append((i, f))
		elif f < chk[-1][1]:
			if i == f:
				ans -= 1
				chk = [(i, f)]
			else:
				while len(chk) > 0 and i < chk[0][1]:
					del chk[0]
				chk.append((i, f))
		elif f == chk[-1][1]:
			if i == f or chk[-1][0] != chk[-1][1] or (len(chk) > 1 and chk[-2][1] == f):
				ans -= 1
			while len(chk) > 0 and i < chk[0][1]:
				del chk[0]
			chk.append((i, f))
	print(ans)


class Node:

	def __init__(self, val, left=None, right=None):
		self.val = val
		self.left = left
		self.right = right

	def __str__(self):
		return '< Node with the value = ' + str(self.val) + ' >'

class Deque:

	def __init__(self):
		self.left = None
		self.right = None

	def is_empty(self):
		return self.left is None

	def push_left(self, val):
		node = Node(val, right=self.left)
		self.left = node
		if self.right is None:
			self.right = node
		else:
			self.left.right.left = node

	def push_right(self, val):
		node = Node(val, left=self.right)
		self.right = node
		if self.left is None:
			self.left = node
		else:
			self.right.left.right = node

	def pop_left(self):
		if self.left is None:
			raise IndexError
		res = self.left.val
		self.left = self.left.right
		if self.left is None:
			self.right = None
		else:
			self.left.left = None
		return res

	def pop_right(self):
		if self.right is None:
			raise IndexError
		res = self.right.val
		self.right = self.right.left
		if self.right is None:
			self.left = None
		else:
			self.right.right = None
		return res
T = int(input())
for query in range(T):
	N = int(input())
	A = [int(v) for v in input().split()]
	B = [int(v) for v in input().split()]
	cuts = Deque()
	count = 0
	for i in range(N):
		if A[i] < B[i]:
			print(-1)
			break
		while not cuts.is_empty() and cuts.left.val > A[i]:
			cuts.pop_left()
		while not cuts.is_empty() and cuts.right.val < B[i]:
			cuts.pop_right()
		if not cuts.is_empty():
			if cuts.right.val > B[i]:
				cuts.push_right(B[i])
				count += 1
		elif A[i] > B[i]:
			cuts.push_right(B[i])
			count += 1
	else:
		print(count)