You play a computer game. In this game, you lead a party of $m$ heroes, and you have to clear a dungeon with $n$ monsters. Each monster is characterized by its power $a_i$. Each hero is characterized by his power $p_i$ and endurance $s_i$.

The heroes clear the dungeon day by day. In the beginning of each day, you choose a hero (exactly one) who is going to enter the dungeon this day.

When the hero enters the dungeon, he is challenged by the first monster which was not defeated during the previous days (so, if the heroes have already defeated $k$ monsters, the hero fights with the monster $k + 1$). When the hero fights the monster, there are two possible outcomes:

  if the monster's power is strictly greater than the hero's power, the hero retreats from the dungeon. The current day ends;  otherwise, the monster is defeated. 

After defeating a monster, the hero either continues fighting with the next monster or leaves the dungeon. He leaves the dungeon either if he has already defeated the number of monsters equal to his endurance during this day (so, the $i$-th hero cannot defeat more than $s_i$ monsters during each day), or if all monsters are defeated — otherwise, he fights with the next monster. When the hero leaves the dungeon, the current day ends.

Your goal is to defeat the last monster. What is the minimum number of days that you need to achieve your goal? Each day you have to use exactly one hero; it is possible that some heroes don't fight the monsters at all. Each hero can be used arbitrary number of times.


-----Input-----

The first line contains one integer $t$ ($1 \le t \le 10^5$) — the number of test cases. Then the test cases follow.

The first line of each test case contains one integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the number of monsters in the dungeon.

The second line contains $n$ integers $a_1$, $a_2$, ..., $a_n$ ($1 \le a_i \le 10^9$), where $a_i$ is the power of the $i$-th monster.

The third line contains one integer $m$ ($1 \le m \le 2 \cdot 10^5$) — the number of heroes in your party.

Then $m$ lines follow, each describing a hero. Each line contains two integers $p_i$ and $s_i$ ($1 \le p_i \le 10^9$, $1 \le s_i \le n$) — the power and the endurance of the $i$-th hero.

It is guaranteed that the sum of $n + m$ over all test cases does not exceed $2 \cdot 10^5$.


-----Output-----

For each test case print one integer — the minimum number of days you have to spend to defeat all of the monsters (or $-1$ if it is impossible).


-----Example-----
Input
2
6
2 3 11 14 1 8
2
3 2
100 1
5
3 5 100 2 3
2
30 5
90 1

Output
5
-1

Difficulty: MEDIUM_HARD
Tags: Sorting

Amortized analysis

Greedy algorithms

Dynamic programming

Data structures
Skill types: Sorting

Amortized analysis

Greedy algorithms

Dynamic programming

Data structures

Starter code:

Solutions:
import os, sys
from io import BytesIO, IOBase

def cons(n, x):
	xx = n.bit_length()
	dp = [[0] * n for _ in range(xx)]
	dp[0] = x
	for i in range(1, xx):
		for j in range(n - (1 << i) + 1):
			dp[i][j] = max(dp[i - 1][j], dp[i - 1][j + (1 << i - 1)])
	return dp

def ask(l, r, dp):
	xx1 = (r - l + 1).bit_length() - 1
	return max(dp[xx1][l], dp[xx1][r - (1 << xx1) + 1])

def solve(n, a):
	day = [0] * (n + 1)
	for _ in range(int(input())):
		(p, s) = map(int, input().split())
		day[s] = max(day[s], p)
	for i in range(n - 1, -1, -1):
		day[i] = max(day[i], day[i + 1])
	if max(a) > day[0]:
		return -1
	dp = cons(n, a)
	(val, i) = (0, 0)
	while i != n:
		(hi, lo, ans) = (n - 1, i, i)
		while hi >= lo:
			mid = (hi + lo) // 2
			maxi = ask(i, mid, dp)
			if day[mid - i + 1] >= maxi:
				lo = mid + 1
				ans = mid
			else:
				hi = mid - 1
		i = ans + 1
		val += 1
	return val

def main():
	for _ in range(int(input())):
		n = int(input())
		a = list(map(int, input().split()))
		print(solve(n, a))
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


import os
import sys
from io import BytesIO, IOBase
from types import GeneratorType
from collections import defaultdict
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
t = int(input())
for i in range(t):
	n = int(input())
	b = list(map(int, input().split()))
	m = int(input())
	st = [0] * (n + 1)
	for j in range(m):
		(p, s) = map(int, input().split())
		st[s] = max(st[s], p)
	j = n - 1
	while j >= 1:
		st[j] = max(st[j + 1], st[j])
		j += -1
	i = 0
	ans = 0
	f = 1
	while i < n:
		j = 0
		m = 0
		if b[i] > st[1]:
			f = 0
			break
		while i + j < n:
			m = max(m, b[i + j])
			if m <= st[j + 1]:
				j += 1
			else:
				break
		i = i + j
		ans += 1
	if f:
		print(ans)
	else:
		print(-1)


import sys
import bisect
sys.setrecursionlimit(10 ** 8)
input = sys.stdin.readline
INF = 10 ** 9

class RMQ:

	def __init__(self, a):
		self.n = len(a)
		self.size = 2 ** (self.n - 1).bit_length()
		self.data = [0] * (2 * self.size - 1)
		self.initialize(a)

	def initialize(self, a):
		for i in range(self.n):
			self.data[self.size + i - 1] = a[i]
		for i in range(self.size - 2, -1, -1):
			self.data[i] = max(self.data[i * 2 + 1], self.data[i * 2 + 2])

	def update(self, k, x):
		k += self.size - 1
		self.data[k] = x
		while k > 0:
			k = (k - 1) // 2
			self.data[k] = max(self.data[2 * k + 1], self.data[2 * k + 2])

	def query(self, l, r):
		L = l + self.size
		R = r + self.size
		s = 0
		while L < R:
			if R & 1:
				R -= 1
				s = max(s, self.data[R - 1])
			if L & 1:
				s = max(s, self.data[L - 1])
				L += 1
			L >>= 1
			R >>= 1
		return s
t = int(input())
for i in range(t):
	n = int(input())
	a = [int(item) for item in input().split()]
	m = int(input())
	brave = []
	for j in range(m):
		(pp, ss) = [int(item) for item in input().split()]
		brave.append((pp, ss))
	brave.sort(reverse=True)
	p = []
	s = []
	for (pp, ss) in brave:
		p.append(pp)
		s.append(ss)
	s_rmq = RMQ(s)
	a_rmq = RMQ(a)
	p.reverse()
	s.reverse()
	max_step = max(s)
	days = 0
	curr = 0
	while curr < n:
		l = 0
		r = min(n - curr, max_step) + 1
		while r - l > 1:
			mid = (l + r) // 2
			max_monster = a_rmq.query(curr, curr + mid)
			index = m - bisect.bisect_left(p, max_monster)
			walkable = s_rmq.query(0, index)
			if walkable >= mid:
				l = mid
			else:
				r = mid
		if l == 0:
			days = -1
			break
		else:
			days += 1
			curr += l
	print(days)


import sys
readline = sys.stdin.readline
mr = lambda : map(int, readline().split())
t = int(readline())
Ans = []
for _ in range(t):
	n = int(readline())
	monsters = list(mr())
	m = int(readline())
	heroes = [tuple(mr()) for _ in range(m)]
	tmp = [0] * (n + 1)
	for x in heroes:
		tmp[x[1]] = max(tmp[x[1]], x[0])
	for i in range(n - 1, -1, -1):
		tmp[i] = max(tmp[i + 1], tmp[i])
	qq = 0
	ans = 0
	while qq < n:
		maxMonsterPower = 0
		j = 0
		for i in range(1, n - qq + 1):
			if maxMonsterPower < monsters[qq + i - 1]:
				maxMonsterPower = monsters[qq + i - 1]
			if tmp[i] < maxMonsterPower:
				break
			j += 1
		if j < 1 and qq < n:
			ans = -1
			break
		qq += j
		ans += 1
	Ans.append(ans)
print('\n'.join(map(str, Ans)))


import os
import sys
import math
from io import BytesIO, IOBase
from fractions import Fraction
import collections
from itertools import permutations
from collections import defaultdict
from collections import deque
import threading
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

class SegmentTree:

	def __init__(self, data, default=0, func=lambda a, b: max(a, b)):
		self._default = default
		self._func = func
		self._len = len(data)
		self._size = _size = 1 << (self._len - 1).bit_length()
		self.data = [default] * (2 * _size)
		self.data[_size:_size + self._len] = data
		for i in reversed(range(_size)):
			self.data[i] = func(self.data[i + i], self.data[i + i + 1])

	def __delitem__(self, idx):
		self[idx] = self._default

	def __getitem__(self, idx):
		return self.data[idx + self._size]

	def __setitem__(self, idx, value):
		idx += self._size
		self.data[idx] = value
		idx >>= 1
		while idx:
			self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
			idx >>= 1

	def __len__(self):
		return self._len

	def query(self, start, stop):
		if start == stop:
			return self.__getitem__(start)
		stop += 1
		start += self._size
		stop += self._size
		res = self._default
		while start < stop:
			if start & 1:
				res = self._func(res, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res = self._func(res, self.data[stop])
			start >>= 1
			stop >>= 1
		return res

	def __repr__(self):
		return 'SegmentTree({0})'.format(self.data)

class SegmentTree1:

	def __init__(self, data, default=10 ** 6, func=lambda a, b: min(a, b)):
		self._default = default
		self._func = func
		self._len = len(data)
		self._size = _size = 1 << (self._len - 1).bit_length()
		self.data = [default] * (2 * _size)
		self.data[_size:_size + self._len] = data
		for i in reversed(range(_size)):
			self.data[i] = func(self.data[i + i], self.data[i + i + 1])

	def __delitem__(self, idx):
		self[idx] = self._default

	def __getitem__(self, idx):
		return self.data[idx + self._size]

	def __setitem__(self, idx, value):
		idx += self._size
		self.data[idx] = value
		idx >>= 1
		while idx:
			self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
			idx >>= 1

	def __len__(self):
		return self._len

	def query(self, start, stop):
		if start == stop:
			return self.__getitem__(start)
		stop += 1
		start += self._size
		stop += self._size
		res = self._default
		while start < stop:
			if start & 1:
				res = self._func(res, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res = self._func(res, self.data[stop])
			start >>= 1
			stop >>= 1
		return res

	def __repr__(self):
		return 'SegmentTree({0})'.format(self.data)
MOD = 10 ** 9 + 7

class Factorial:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorials = [1, 1]
		self.invModulos = [0, 1]
		self.invFactorial_ = [1, 1]

	def calc(self, n):
		if n <= -1:
			print('Invalid argument to calculate n!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.factorials):
			return self.factorials[n]
		nextArr = [0] * (n + 1 - len(self.factorials))
		initialI = len(self.factorials)
		prev = self.factorials[-1]
		m = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * i % m
		self.factorials += nextArr
		return self.factorials[n]

	def inv(self, n):
		if n <= -1:
			print('Invalid argument to calculate n^(-1)')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		p = self.MOD
		pi = n % p
		if pi < len(self.invModulos):
			return self.invModulos[pi]
		nextArr = [0] * (n + 1 - len(self.invModulos))
		initialI = len(self.invModulos)
		for i in range(initialI, min(p, n + 1)):
			next = -self.invModulos[p % i] * (p // i) % p
			self.invModulos.append(next)
		return self.invModulos[pi]

	def invFactorial(self, n):
		if n <= -1:
			print('Invalid argument to calculate (n^(-1))!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.invFactorial_):
			return self.invFactorial_[n]
		self.inv(n)
		nextArr = [0] * (n + 1 - len(self.invFactorial_))
		initialI = len(self.invFactorial_)
		prev = self.invFactorial_[-1]
		p = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * self.invModulos[i % p] % p
		self.invFactorial_ += nextArr
		return self.invFactorial_[n]

class Combination:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorial = Factorial(MOD)

	def ncr(self, n, k):
		if k < 0 or n < k:
			return 0
		k = min(k, n - k)
		f = self.factorial
		return f.calc(n) * f.invFactorial(max(n - k, k)) * f.invFactorial(min(k, n - k)) % self.MOD
mod = 10 ** 9 + 7
omod = 998244353
prime = [True for i in range(10)]
pp = [0] * 10

def SieveOfEratosthenes(n=10):
	p = 2
	c = 0
	while p * p <= n:
		if prime[p] == True:
			c += 1
			for i in range(p, n + 1, p):
				pp[i] += 1
				prime[i] = False
		p += 1

def binarySearch(arr, n, key):
	left = 0
	right = n - 1
	mid = 0
	res = 0
	while left <= right:
		mid = (right + left) // 2
		if arr[mid][0] > key:
			right = mid - 1
		else:
			res = mid
			left = mid + 1
	return res
t = int(input())
for i in range(t):
	n = int(input())
	powmon = [int(i) for i in input().split()]
	m = int(input())
	l = [0] * (n + 1)
	for i in range(m):
		(p, s) = map(int, input().split())
		l[s] = max(l[s], p)
	for i in range(n - 1, -1, -1):
		l[i] = max(l[i + 1], l[i])
	ans = 1
	cnt = 1
	ma = 0
	if l[1] < max(powmon):
		print(-1)
	else:
		for i in powmon:
			ma = max(ma, i)
			if l[cnt] < ma:
				cnt = 1
				ans += 1
				ma = i
			cnt += 1
		print(ans)


cases = int(input())
for c in range(cases):
	n_monsters = int(input())
	powers_mons = [int(x) for x in input().split()]
	heroes = int(input())
	hero_power = []
	hero_endurance = []
	for i in range(heroes):
		(x, y) = map(int, input().split())
		hero_power.append(x)
		hero_endurance.append(y)
	optimal = [0 for i in range(n_monsters + 1)]
	for i in range(heroes):
		optimal[hero_endurance[i]] = max(optimal[hero_endurance[i]], hero_power[i])
	for i in range(n_monsters, 0, -1):
		optimal[i - 1] = max(optimal[i], optimal[i - 1])
	x = 0
	result = 0
	killed = 0
	while killed != n_monsters:
		prev = killed
		cur_power = powers_mons[killed]
		x = 1
		while optimal[x] >= cur_power:
			x += 1
			killed += 1
			if killed == n_monsters:
				break
			cur_power = max(cur_power, powers_mons[killed])
		if killed != prev:
			result += 1
			continue
		result = -1
		break
	print(result)


from sys import stdin
from collections import Counter, deque
input = stdin.buffer.readline
T = int(input())
for _ in range(T):
	(n, mon) = (int(input()), list(map(int, input().split())))
	(m, hro) = (int(input()), [])
	for _ in range(m):
		(p, s) = map(int, input().split())
		hro.append((s, p))
	hro.sort(reverse=True)
	ls = []
	for (s, p) in hro:
		if not ls or p > ls[-1][1]:
			ls.append((s, p))
	(hro, m) = (list(reversed(ls)), len(ls))
	if max(mon) > hro[0][1]:
		print(-1)
		continue
	day = 0
	(dur, pwr, p, mx) = (*hro[0], 0, 0)
	for u in mon:
		mx = max(mx, u)
		if dur > 0 and pwr >= mx:
			dur -= 1
			continue
		if dur == 0 and p + 1 < m and (hro[p + 1][1] >= mx):
			(ndur, npwr, cdur) = (*hro[p + 1], hro[p][0])
			(dur, pwr, p) = (ndur - cdur - 1, npwr, p + 1)
			continue
		day += 1
		(dur, pwr, p, mx) = (hro[0][0] - 1, hro[0][1], 0, u)
	print(day + 1)


import sys
input = sys.stdin.readline
import bisect
t = int(input())
for i in range(t):
	n = int(input())
	powmon = [int(i) for i in input().split()]
	m = int(input())
	l = [0] * (n + 1)
	for i in range(m):
		(p, s) = map(int, input().split())
		l[s] = max(l[s], p)
	for i in range(n - 1, -1, -1):
		l[i] = max(l[i + 1], l[i])
	ans = 1
	cnt = 1
	ma = 0
	if l[1] < max(powmon):
		print(-1)
	else:
		for i in powmon:
			ma = max(ma, i)
			if l[cnt] < ma:
				cnt = 1
				ans += 1
				ma = i
			cnt += 1
		print(ans)


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from bisect import bisect_left, bisect_right
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	ma = max(a)
	mb = 0
	m = int(input())
	di = {}
	for __ in range(m):
		(p, s) = map(int, input().split())
		if s not in di:
			di[s] = [p]
		else:
			di[s] += [p]
		mb = max(mb, p)
	if mb < ma:
		print(-1)
		continue
	every = sorted([each for each in di])
	(x, y) = ([0] * m, [0] * m)
	c = 0
	for s in every:
		for p in di[s]:
			y[c] = p
			x[c] = s
			c += 1
	sit = [0] * m
	sit[m - 1] = y[m - 1]
	for i in range(m - 2, -1, -1):
		sit[i] = max(sit[i + 1], y[i])
	ans = 0
	streak = 0
	curmax = 0
	streak_index = [-1] * (n + 1)
	streak_index[1] = 0
	cur = 1
	for i in range(m):
		next = x[i]
		if next > cur:
			for j in range(cur + 1, min(next + 1, n + 1)):
				streak_index[j] = i
			cur = min(next, n)
		if cur == n:
			break
	for i in range(n):
		next = a[i]
		curmax = max(curmax, next)
		streak += 1
		index = streak_index[streak]
		if index != -1 and sit[index] >= curmax:
			continue
		else:
			ans += 1
			streak = 1
			curmax = next
	print(ans + 1)


o = int(input())
for _ in range(0, o):
	n = int(input())
	lis = [0] + list(map(int, input().split()))
	m = int(input())
	l = [0] * (n + 1)
	for i in range(0, m):
		(p, s) = map(int, input().split())
		l[s] = max(l[s], p)
	for i in range(n - 1, -1, -1):
		l[i] = max(l[i], l[i + 1])
	k = 0
	ans = 0
	while k < n:
		q = 0
		t = 0
		while k + t + 1 <= n and l[t + 1] >= max(q, lis[k + t + 1]):
			q = max(q, lis[k + t + 1])
			t += 1
		if t == 0:
			ans = -1
			break
		k += t
		ans += 1
	print(ans)


import sys
from bisect import bisect_left

def input():
	return sys.stdin.readline().strip()

def list2d(a, b, c):
	return [[c] * b for i in range(a)]

def list3d(a, b, c, d):
	return [[[d] * c for j in range(b)] for i in range(a)]

def list4d(a, b, c, d, e):
	return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]

def ceil(x, y=1):
	return int(-(-x // y))

def INT():
	return int(input())

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

def LIST(N=None):
	return list(MAP()) if N is None else [INT() for i in range(N)]

def Yes():
	print('Yes')

def No():
	print('No')

def YES():
	print('YES')

def NO():
	print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

class SegTree:

	def __init__(self, n, func, intv, A=[]):
		self.n = n
		self.func = func
		self.intv = intv
		n2 = 1
		while n2 < n:
			n2 <<= 1
		self.n2 = n2
		self.tree = [self.intv] * (n2 << 1)
		if A:
			for i in range(n):
				self.tree[n2 + i] = A[i]
			for i in range(n2 - 1, -1, -1):
				self.tree[i] = self.func(self.tree[i * 2], self.tree[i * 2 + 1])

	def update(self, i, x):
		i += self.n2
		self.tree[i] = x
		while i > 0:
			i >>= 1
			self.tree[i] = self.func(self.tree[i * 2], self.tree[i * 2 + 1])

	def query(self, a, b):
		l = a + self.n2
		r = b + self.n2
		s = self.intv
		while l < r:
			if r & 1:
				r -= 1
				s = self.func(s, self.tree[r])
			if l & 1:
				s = self.func(s, self.tree[l])
				l += 1
			l >>= 1
			r >>= 1
		return s

	def get(self, i):
		return self.tree[i + self.n2]

	def all(self):
		return self.tree[1]

def bisearch_max(mn, mx, func):
	ok = mn
	ng = mx
	while ok + 1 < ng:
		mid = (ok + ng) // 2
		if func(mid):
			ok = mid
		else:
			ng = mid
	return ok

def check(m):
	mx = st.query(cur, m)
	idx = bisect_left(P, mx)
	if idx == M:
		return False
	(_, s) = PS[idx]
	scnt = m - cur
	return s >= scnt
ans = []
for _ in range(INT()):
	N = INT()
	A = LIST()
	M = INT()
	PS = []
	for i in range(M):
		(p, s) = MAP()
		PS.append((p, s))
	PS.sort()
	for i in range(M - 1, 0, -1):
		if PS[i][1] > PS[i - 1][1]:
			PS[i - 1] = (PS[i - 1][0], PS[i][1])
	(P, _) = zip(*PS)
	st = SegTree(N, max, 0, A)
	cur = day = 0
	while cur < N:
		res = bisearch_max(cur, N + 1, check)
		if res == cur:
			ans.append(str(-1))
			break
		cur = res
		day += 1
	else:
		ans.append(str(day))
print('\n'.join(ans))


from sys import *
input = stdin.readline
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	d = [0 for i in range(n + 1)]
	for i in range(int(input())):
		(p, e) = map(int, input().split())
		d[e] = max(d[e], p)
	for i in range(n - 1, -1, -1):
		d[i] = max(d[i], d[i + 1])
	if d[1] < max(l):
		print(-1)
		continue
	(days, curr, m) = (1, 1, 0)
	for i in l:
		m = max(i, m)
		if d[curr] < m:
			days += 1
			curr = 1
			m = i
		curr += 1
	print(days)


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split(' ')))
	m = int(input())
	heroes = [0 for i in range(n + 1)]
	for i in range(m):
		(p, e) = map(int, input().split())
		heroes[e] = max(heroes[e], p)
	for i in range(n - 1, -1, -1):
		heroes[i] = max(heroes[i], heroes[i + 1])
	if max(l) > heroes[0]:
		print(-1)
	else:
		ans = 1
		c = 1
		ma = 0
		for i in l:
			ma = max(i, ma)
			if heroes[c] < ma:
				ans += 1
				c = 1
				ma = i
			c += 1
		print(ans)


import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
for _ in range(int(input())):
	n = int(input())
	a = [int(i) for i in input().split()]
	m = int(input())
	p = []
	s = []
	mp = 0
	for i in range(m):
		(pi, si) = [int(i) for i in input().split()]
		if si:
			mp = max(mp, pi)
		p.append(pi)
		s.append(si)
	ma = max(a)
	if ma > mp:
		print(-1)
		continue
	v = [0] * (max(n, m) + 1)
	for i in range(m):
		v[s[i]] = max(v[s[i]], p[i])
	for i in range(len(v) - 2, -1, -1):
		v[i] = max(v[i], v[i + 1])
	num = 1
	po = 0
	ans = 0
	i = 0
	while i < n:
		po = max(po, a[i])
		if v[num] >= po:
			num += 1
			i += 1
		else:
			ans += 1
			num = 1
			po = a[i]
	if num:
		ans += 1
	print(ans)


import sys
input = sys.stdin.readline
from bisect import bisect_left
Q = int(input())
Query = []
for _ in range(Q):
	N = int(input())
	A = list(map(int, input().split()))
	M = int(input())
	state = [list(map(int, input().split())) for _ in range(M)]
	Query.append((N, A, M, state))
for (N, A, M, state) in Query:
	state.sort()
	P = []
	S = []
	for (p, s) in state:
		P.append(p)
		S.append(s)
	for i in reversed(range(M - 1)):
		S[i] = max(S[i], S[i + 1])
	ans = 0
	now = 10 ** 12
	tm_max = 0
	for a in reversed(A):
		i = bisect_left(P, max(a, tm_max))
		if i == M:
			ans = -1
			break
		if now + 1 > S[i]:
			tm_max = a
			now = 1
			ans += 1
		else:
			tm_max = max(tm_max, a)
			now += 1
	print(ans)


from sys import stdin
t = int(stdin.readline())
for _ in range(t):
	n = int(stdin.readline())
	x = list(map(int, stdin.readline().split()))
	m = int(stdin.readline())
	(v, v2) = ([], [])
	for i in range(m):
		(p, s) = map(int, stdin.readline().split())
		v2.append([p, s])
	v2.sort()
	for i in range(m - 1, -1, -1):
		if i == m - 1 or (v2[i][0] != v2[i + 1][0] and v2[i][1] != v2[i + 1][1]):
			v.append(v2[i])
	m = len(v)
	(ans, count, pointer, ma) = (1, 0, 0, 0)
	for i in range(n):
		count += 1
		ma = max(ma, x[i])
		if x[i] > v[0][0]:
			ans = -1
			break
		if count <= v[pointer][1]:
			pass
		else:
			while pointer < m and v[pointer][1] < count:
				pointer += 1
				if pointer < m and v[pointer][0] < ma:
					break
		if pointer >= m or v[pointer][1] < count or v[pointer][0] < ma:
			(pointer, count) = (0, 1)
			ans += 1
			ma = x[i]
	print(ans)


mod = 10 ** 9 + 7
import sys
sys.setrecursionlimit(10 ** 6)
from sys import stdin, stdout
import bisect
from bisect import bisect_left as bl
from bisect import bisect_right as br
import itertools
import collections
import math
import heapq
import random

def modinv(n, p):
	return pow(n, p - 2, p)

def ncr(n, r, p):
	t = fact[n] * (ifact[r] * ifact[n - r] % p) % p
	return t

def cin():
	return map(int, sin().split())

def ain():
	return list(map(int, sin().split()))

def sin():
	return input()

def inin():
	return int(input())

def GCD(x, y):
	while y:
		(x, y) = (y, x % y)
	return x

def main():
	t = inin()
	for _ in range(t):
		n = inin()
		a = ain()
		m = inin()
		p = []
		e = []
		d = {}
		for i in range(m):
			(j, k) = cin()
			p.append((j, k))
		p.sort(reverse=True)
		x = 0
		for i in p:
			if i[1] > x:
				e.append(i)
			x = max(x, i[1])
		y = n - 1
		p = []
		for i in e:
			p.append(i[0])
			d[i[0]] = i[1]
		p.sort()
		nn = len(p)
		ans = 0
		b = []
		m = 0
		j = 0
		for i in a:
			m = max(i, m)
			j += 1
			x = bisect.bisect_right(p, m - 1, 0, nn - 1)
			if m > p[x]:
				ans = -2
				break
			if j > d[p[x]]:
				ans += 1
				j = 1
				m = i
		print(ans + 1)
py2 = round(0.5)
if py2:
	from future_builtins import ascii, filter, hex, map, oct, zip
	range = xrange
import os, sys
from io import IOBase, BytesIO
BUFSIZE = 8192

class FastIO(BytesIO):
	newlines = 0

	def __init__(self, file):
		self._file = file
		self._fd = file.fileno()
		self.writable = 'x' in file.mode or 'w' in file.mode
		self.write = super(FastIO, self).write if self.writable else None

	def _fill(self):
		s = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
		self.seek((self.tell(), self.seek(0, 2), super(FastIO, self).write(s))[0])
		return s

	def read(self):
		while self._fill():
			pass
		return super(FastIO, self).read()

	def readline(self):
		while self.newlines == 0:
			s = self._fill()
			self.newlines = s.count(b'\n') + (not s)
		self.newlines -= 1
		return super(FastIO, self).readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.getvalue())
			(self.truncate(0), self.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		if py2:
			self.write = self.buffer.write
			self.read = self.buffer.read
			self.readline = self.buffer.readline
		else:
			self.write = lambda s: self.buffer.write(s.encode('ascii'))
			self.read = lambda : self.buffer.read().decode('ascii')
			self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
import sys

class ostream:

	def __lshift__(self, a):
		sys.stdout.write(str(a))
		return self
cout = ostream()
endl = '\n'

def readnumbers(zero=0):
	conv = ord if py2 else lambda x: x
	A = []
	numb = zero
	sign = 1
	i = 0
	s = sys.stdin.buffer.read()
	try:
		while True:
			if s[i] >= b'0'[0]:
				numb = 10 * numb + conv(s[i]) - 48
			elif s[i] == b'-'[0]:
				sign = -1
			elif s[i] != b'\r'[0]:
				A.append(sign * numb)
				numb = zero
				sign = 1
			i += 1
	except:
		pass
	if s and s[-1] >= b'0'[0]:
		A.append(sign * numb)
	return A
main()


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	m = int(input())
	p = []
	s = []
	for i in range(m):
		(x, y) = map(int, input().split())
		p.append(x)
		s.append(y)
	bst = [0 for i in range(n + 1)]
	for i in range(m):
		bst[s[i]] = max(bst[s[i]], p[i])
	for i in range(n - 1, -1, -1):
		bst[i] = max(bst[i + 1], bst[i])
	x = 0
	cnt = 0
	mst = 0
	while mst != n:
		prev = mst
		m_p = a[mst]
		x = 1
		while m_p <= bst[x]:
			x += 1
			mst += 1
			if mst == n:
				break
			m_p = max(m_p, a[mst])
		if mst == prev:
			cnt = -1
			break
		cnt += 1
	print(cnt)


import sys
from array import array
import typing as Tp

def input():
	return sys.stdin.buffer.readline().decode('utf-8')

def main():
	t = int(input())
	ans = [-1] * t
	for ti in range(t):
		n = int(input())
		mons = list(map(int, input().split()))
		m = int(input())
		heroes = [0] * (n + 1)
		for (pi, si) in (map(int, input().split()) for _ in range(m)):
			heroes[si] = max(heroes[si], pi)
		for i in range(n - 1, -1, -1):
			if heroes[i] < heroes[i + 1]:
				heroes[i] = heroes[i + 1]
		(day, mons_i, hero_i) = (1, 0, 1)
		max_mons_pow = 0
		while mons_i < n:
			max_mons_pow = max(max_mons_pow, mons[mons_i])
			if heroes[hero_i] < max_mons_pow:
				if hero_i == 1:
					break
				hero_i = 1
				day += 1
				max_mons_pow = 0
			else:
				mons_i += 1
				hero_i += 1
		else:
			ans[ti] = day
	sys.stdout.buffer.write(('\n'.join(map(str, ans)) + '\n').encode('utf-8'))
main()


import sys
input = sys.stdin.readline
t = int(input())
while t:
	t -= 1
	n = int(input())
	a = list(map(int, input().split()))
	m = int(input())
	heros = []
	for _ in range(m):
		(p, e) = map(int, input().split())
		heros.append((p, e))
	bst = [0] * n
	for (p, e) in heros:
		bst[e - 1] = max(p, bst[e - 1])
	for i in range(n - 2, -1, -1):
		bst[i] = max(bst[i + 1], bst[i])
	td = 0
	days = 0
	while td < n:
		streak = 0
		max_def = a[td + streak]
		while td + streak < n and max(max_def, a[td + streak]) <= bst[streak]:
			max_def = max(max_def, a[td + streak])
			streak += 1
		if not streak:
			print(-1)
			break
		days += 1
		td += streak
		streak = 0
	else:
		print(days)


import sys
input = sys.stdin.readline
t = int(input())
ANS = []
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	m = int(input())
	ps = [list(map(int, input().split())) for _ in range(m)]
	p = [0] * (n + 1)
	for i in range(m):
		p[ps[i][1]] = max(p[ps[i][1]], ps[i][0])
	for i in range(n)[::-1]:
		p[i] = max(p[i], p[i + 1])
	if p[1] < max(a):
		ANS.append(-1)
		continue
	ans = 0
	mx = 0
	cnt = 0
	i = 0
	for x in a:
		cnt += 1
		mx = max(mx, x)
		if p[cnt] < mx:
			ans += 1
			mx = x
			cnt = 1
	if cnt:
		ans += 1
	ANS.append(ans)
print('\n'.join(map(str, ANS)))


import sys
input = sys.stdin.readline

def init_min(init_min_val):
	for i in range(n):
		seg_min[i + num_min - 1] = init_min_val[i]
	for i in range(num_min - 2, -1, -1):
		seg_min[i] = min(seg_min[2 * i + 1], seg_min[2 * i + 2])

def update_min(k, x):
	k += num_min - 1
	seg_min[k] = x
	while k:
		k = (k - 1) // 2
		seg_min[k] = min(seg_min[k * 2 + 1], seg_min[k * 2 + 2])

def query_min(p, q):
	if q <= p:
		return ide_ele_min
	p += num_min - 1
	q += num_min - 2
	res = ide_ele_min
	while q - p > 1:
		if p & 1 == 0:
			res = min(res, seg_min[p])
		if q & 1 == 1:
			res = min(res, seg_min[q])
			q -= 1
		p = p // 2
		q = (q - 1) // 2
	if p == q:
		res = min(res, seg_min[p])
	else:
		res = min(min(res, seg_min[p]), seg_min[q])
	return res
qq = int(input())
for testcases in [0] * qq:
	n = int(input())
	a = list(map(int, input().split()))
	for i in range(n):
		a[i] *= -1
	m = int(input())
	p = [-1] * n
	for _ in [0] * m:
		(x, y) = map(int, input().split())
		p[y - 1] = max(p[y - 1], x)
	tmp_max = -1
	for i in range(n - 1, -1, -1):
		tmp_max = max(tmp_max, p[i])
		p[i] = tmp_max
	if p[0] < -min(a):
		print(-1)
		continue
	ide_ele_min = 1
	num_min = 2 ** (n - 1).bit_length()
	seg_min = [ide_ele_min] * 2 * num_min
	init_min(a)
	start = 0
	res = 0
	while start < n:
		ok = 0
		ng = n - start
		while ng - ok > 1:
			mid = (ok + ng) // 2
			if -query_min(start, start + mid + 1) <= p[mid]:
				ok = mid
			else:
				ng = mid
		res += 1
		start += ok + 1
	print(res)


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	m = int(input())
	b = [tuple(map(int, input().split())) for __ in range(m)]
	ans = 1
	mx = [0] * (n + 1)
	for (p, s) in b:
		mx[s] = max(mx[s], p)
	for i in range(n - 1, -1, -1):
		mx[i] = max(mx[i], mx[i + 1])
	if mx[1] < max(a):
		print(-1)
	else:
		index = 1
		ma = 0
		for mon in a:
			ma = max(mon, ma)
			if mx[index] < ma:
				index = 1
				ans += 1
				ma = mon
			index += 1
		print(ans)


from __future__ import division, print_function
import bisect

def main():
	import sys
	data = iter(map(int, sys.stdin.buffer.read().decode('ascii').split()))
	t = next(data)
	res = [-1] * t
	for testid in range(t):
		n = next(data)
		a = [next(data) for i in range(n)]
		m = next(data)
		(p, s) = map(list, zip(*((next(data), next(data)) for i in range(m))))
		index = list(range(m))
		index.sort(key=lambda index: (p[index], s[index]), reverse=True)
		pp = []
		ss = []
		smax = 0
		for (pos, i) in enumerate(index):
			if pos == 0 or (p[i] < pp[-1] and s[i] > smax):
				pp.append(p[i])
				ss.append(s[i])
				smax = max(smax, s[i])
		m = len(pp)
		index = p = s = None
		j = 0
		tmp_s = 1
		maxa = 10 ** 9 + 1
		tmp_res = 0
		for ai in a:
			maxa = max(maxa, ai)
			if maxa > pp[j]:
				maxa = ai
				tmp_res += 1
				j = 0
				tmp_s = 1
			if maxa <= pp[j]:
				tmp_s += 1
				if tmp_s > ss[j]:
					if j < m - 1:
						j = j + 1
					else:
						maxa = 10 ** 9 + 1
				if tmp_s > ss[j]:
					while j < m - 1:
						j = j + 1
						if tmp_s <= ss[j]:
							break
					else:
						maxa = 10 ** 9 + 1
			else:
				tmp_res = -1
				break
		res[testid] = tmp_res
	sys.stdout.buffer.write('\n'.join((str(x) for x in res)).encode('ascii'))
	return 0
main()


import sys
input = sys.stdin.readline
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	h = int(input())
	he = []
	dp = [0] * (n + 2)
	for _ in range(h):
		(p, s) = list(map(int, input().split()))
		he.append([p, s])
		dp[s] = max(dp[s], p)
	for i in range(n + 1 - 1, -1, -1):
		dp[i] = max(dp[i], dp[i + 1])
	i = 0
	flag = 1
	total = 0
	while i <= n - 1:
		m = 0
		for j in range(i, n + 1):
			if j >= n:
				break
			m = max(m, a[j])
			if m > dp[j - i + 1]:
				break
		total += 1
		if j == i:
			flag = 0
			break
		i = j
	if flag == 0:
		print(-1)
	else:
		print(total)


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
import math
from collections import Counter
import math
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	m = int(input())
	d = [0] * (n + 1)
	for i in range(m):
		(u, v) = map(int, input().split())
		d[v] = max(d[v], u)
	for i in range(n - 1, -1, -1):
		d[i] = max(d[i], d[i + 1])
	ans = 1
	cnt = 1
	ma = 0
	if d[1] < max(arr):
		ans = -1
	else:
		for i in arr:
			ma = max(ma, i)
			if d[cnt] < ma:
				cnt = 1
				ans += 1
				ma = i
			cnt += 1
	print(ans)


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
import bisect

def most(index, monst, power, endu):
	monsofar = 0
	ind1 = index
	prev = 0
	prevpow = 0
	for s in range(index, n):
		monster = monst[s]
		ind = min(bisect.bisect_left(power, max(monster, prevpow)), len(power) - 1)
		if s == index:
			prev = endu[ind]
			prevpow = power[ind]
		if min(endu[ind], prev) >= monsofar + 1:
			prev = endu[ind]
			prevpow = max(power[ind], prevpow)
			monsofar += 1
			ind1 = s
		else:
			break
	return ind1
testcases = int(input())
for j in range(testcases):
	n = int(input())
	monst = list(map(int, input().split()))
	m = int(input())
	hero = []
	for s in range(m):
		(p, s) = map(int, input().split())
		hero.append((p, s))
	hero.sort(key=lambda x: x[0])
	hero.reverse()
	power = []
	endu = []
	for s in range(m):
		h1 = hero[s]
		if s == 0:
			power.append(h1[0])
			endu.append(h1[1])
		elif h1[1] > endu[-1]:
			power.append(h1[0])
			endu.append(h1[1])
	power.reverse()
	endu.reverse()
	days = 0
	index = 0
	while index < n:
		index = most(index, monst, power, endu) + 1
		days += 1
	if power[-1] < max(monst):
		print(-1)
	else:
		print(days)


import sys
from collections import defaultdict as dd
from collections import deque
from fractions import Fraction as f

def eprint(*args):
	print(*args, file=sys.stderr)
zz = 1
from math import *
import copy
if zz:
	input = sys.stdin.readline
else:
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('all.txt', 'w')

def li():
	return [int(x) for x in input().split()]

def fi():
	return int(input())

def si():
	return list(input().rstrip())

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

def gh():
	sys.stdout.flush()

def bo(i):
	return ord(i) - ord('a')
from copy import *
from bisect import *
from itertools import permutations

def bs(p, a, j, m, maxi):
	l = 0
	r = m - 1
	ans = -1
	while l <= r:
		mid = l + (r - l) // 2
		if ff[mid][0] >= p:
			l = mid + 1
			ans = g[mid]
		else:
			r = mid - 1
	return ans
t = fi()
while t > 0:
	t -= 1
	n = fi()
	a = li()
	m = fi()
	d = []
	for i in range(m):
		(p, s) = mi()
		d.append([p, s])
	d.sort(reverse=True)
	ff = []
	for i in range(m):
		ff.append([d[i][1], d[i][0], i])
	ff.sort(reverse=True)
	g = [0 for i in range(m)]
	maxi = -1
	for i in range(m):
		if ff[i][1] > maxi:
			g[i] = ff[i][2]
			maxi = ff[i][1]
		else:
			g[i] = g[i - 1]
	i = j = tle = 0
	while i < n:
		maxi = a[i]
		p = i
		j = 0
		while i < n and j < m:
			maxi = max(maxi, a[i])
			if maxi > d[j][0]:
				break
			if i - p >= d[j][1]:
				j = bs(i - p + 1, d, j, m, maxi)
				if j == -1:
					break
				i -= 1
			i += 1
		tle += 1
		if tle == n:
			break
	print(tle if i == n else -1)


from bisect import bisect_right
from bisect import bisect_left
from collections import defaultdict
from math import sqrt, factorial, gcd, log2, inf, ceil
import sys
input = sys.stdin.readline

def binary(la, start, end, x):
	while start < end:
		mid = (start + end) // 2
		if la[mid][0] > x:
			end = mid - 1
		elif la[mid][0] == x:
			return mid
		else:
			start = mid + 1
	if la[start][0] >= x:
		return start
	return start + 1
t = int(input())
for _ in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	m = int(input())
	la = []
	for i in range(m):
		(a, b) = map(int, input().split())
		la.append([a, b])
	la.sort()
	pref = []
	pref.append(len(la) - 1)
	maxi = la[-1][1]
	for i in range(len(la) - 2, -1, -1):
		maxi = max(maxi, la[i][1])
		if maxi == la[i][1]:
			pref.append(i)
		else:
			pref.append(pref[-1])
	pref.reverse()
	j = 0
	flag = 0
	ans = 0
	flag1 = 0
	while True:
		maxi = 0
		for i in range(j, n):
			maxi = max(maxi, l[i])
			if maxi > la[-1][0]:
				flag = 1
				break
			z = binary(la, 0, len(la) - 1, maxi)
			ka = la[pref[z]][1]
			if ka < i - j + 1:
				ans += 1
				j = i
				break
			elif i == n - 1:
				ans += 1
				flag1 = 1
				break
		if flag1 == 1:
			break
		if flag == 1:
			break
	if flag == 1:
		print(-1)
	else:
		print(ans)


import sys
input = sys.stdin.readline
import bisect
t = int(input())
for testcases in range(t):
	n = int(input())
	A = list(map(int, input().split()))
	m = int(input())
	PS = [tuple(map(int, input().split())) for i in range(m)]
	PS.sort()
	K = [PS[-1]]
	for (a, b) in PS[::-1][1:]:
		if b <= K[-1][1]:
			continue
		else:
			K.append((a, b))
	K.reverse()
	ANS = 1
	count = 0
	countmax = n + 1
	LEN = len(K)
	for a in A:
		x = bisect.bisect_left(K, (a, 0))
		if x == LEN:
			print(-1)
			break
		elif K[x][1] >= count + 1 and countmax >= count + 1:
			count += 1
			countmax = min(countmax, K[x][1])
		else:
			ANS += 1
			count = 1
			countmax = K[x][1]
	else:
		print(ANS)


import math
import sys
from bisect import bisect_right as bs
for _ in range(int(input())):
	n = int(sys.stdin.readline())
	a = list(map(int, sys.stdin.readline().split()))
	m = int(input())
	ma = -1
	h = [0] * (n + 1)
	for i in range(m):
		(x, y) = map(int, sys.stdin.readline().split())
		ma = max(ma, x)
		h[y] = max(h[y], x)
	for i in range(n - 1, 0, -1):
		h[i] = max(h[i + 1], h[i])
	if ma < max(a):
		print(-1)
	else:
		ma = -1
		prev = 0
		ans = 1
		i = 0
		while i < n:
			ma = max(a[i], ma)
			if h[i - prev + 1] < ma:
				prev = i
				ans += 1
				ma = -1
			else:
				i += 1
		print(ans)


import sys
for _ in range(int(input())):
	n = int(sys.stdin.readline())
	mons = list(map(int, sys.stdin.readline().split()))
	m = int(sys.stdin.readline())
	_heros = sorted((tuple(map(int, sys.stdin.readline().split())) for _ in range(m)), reverse=True)
	max_s = 0
	pows = []
	endu = []
	for i in range(m):
		if max_s >= _heros[i][1]:
			continue
		max_s = max(max_s, _heros[i][1])
		pows.append(_heros[i][0])
		endu.append(_heros[i][1])
	pows.append(0)
	endu.append(10 ** 9)
	i = 0
	for ans in range(1, 10 ** 9):
		hero_i = 0
		power = pows[0]
		mons_power = 0
		if power < mons[i]:
			print(-1)
			break
		for j in range(1, n - i + 1):
			if endu[hero_i] < j:
				hero_i += 1
				power = pows[hero_i]
			mons_power = max(mons_power, mons[i])
			if power < mons_power:
				break
			i += 1
		else:
			print(ans)
			break


from bisect import bisect_left as bl
import sys
input = sys.stdin.readline
for _ in range(int(input())):
	n = int(input())
	monsters = list(map(int, input().split()))
	h = int(input())
	l = []
	for i in range(h):
		(x, y) = map(int, input().split())
		l += [[x, y]]
	l.sort()
	end = l[-1][1]
	po = l[-1][0]
	x = [[l[-1][0], l[-1][1]]]
	for i in range(h - 2, -1, -1):
		if end >= l[i][1]:
			pass
		else:
			x += [[l[i][0], l[i][1]]]
			end = l[i][1]
	x.reverse()
	po = [i[0] for i in x]
	end = [i[1] for i in x]
	if max(po) < max(monsters):
		print(-1)
	else:
		maxpo = monsters[-1]
		endreq = 0
		ans = 0
		for i in range(n - 1, -1, -1):
			maxpo = max(monsters[i], maxpo)
			if bl(po, maxpo) == len(po):
				ans += 1
				endreq = 1
				maxpo = monsters[i]
			elif end[bl(po, maxpo)] < endreq + 1:
				ans += 1
				endreq = 1
				maxpo = monsters[i]
			else:
				endreq += 1
		if endreq != 0:
			ans += 1
		print(ans)


from sys import stdin
input = stdin.readline
from bisect import *
t = int(input())
while t:
	n = int(input())
	a = list(map(int, input().split()))
	m = int(input())
	p = []
	mx = max(a)
	flag = 0
	for i in range(m):
		(x, y) = map(int, input().split())
		if x >= mx:
			flag = 1
		p.append([y, x])
	if not flag:
		print(-1)
		t -= 1
		continue
	p.sort(reverse=True)
	pre = 0
	np = []
	for (x, y) in p:
		if pre and y <= pre:
			continue
		pre = y
		np.append([y, x])
	ans = 0
	i = 0
	inf = float('inf')
	while i < n:
		cnt = 0
		mx = 0
		flag = 0
		for j in range(i, n):
			mx = max(mx, a[j])
			pos = bisect_left(np, [mx, -inf])
			if np[pos][1] < j - i + 1:
				ans += 1
				i = j
				flag = 1
				break
		if not flag:
			ans += 1
			break
	print(ans)
	t -= 1


import sys, os, io

def rs():
	return sys.stdin.readline().rstrip()

def ri():
	return int(sys.stdin.readline())

def ria():
	return list(map(int, sys.stdin.readline().split()))

def ws(s):
	sys.stdout.write(s + '\n')

def wi(n):
	sys.stdout.write(str(n) + '\n')

def wia(a):
	sys.stdout.write(' '.join([str(x) for x in a]) + '\n')
import math, datetime, functools, itertools, operator, bisect, fractions, statistics
from collections import deque, defaultdict, OrderedDict, Counter
from fractions import Fraction
from decimal import Decimal
from sys import stdout
from heapq import heappush, heappop, heapify, _heapify_max, _heappop_max, nsmallest, nlargest
INF = 999999999999999999999999
alphabets = 'abcdefghijklmnopqrstuvwxyz'

class SortedList:

	def __init__(self, iterable=[], _load=200):
		values = sorted(iterable)
		self._len = _len = len(values)
		self._load = _load
		self._lists = _lists = [values[i:i + _load] for i in range(0, _len, _load)]
		self._list_lens = [len(_list) for _list in _lists]
		self._mins = [_list[0] for _list in _lists]
		self._fen_tree = []
		self._rebuild = True

	def _fen_build(self):
		self._fen_tree[:] = self._list_lens
		_fen_tree = self._fen_tree
		for i in range(len(_fen_tree)):
			if i | i + 1 < len(_fen_tree):
				_fen_tree[i | i + 1] += _fen_tree[i]
		self._rebuild = False

	def _fen_update(self, index, value):
		if not self._rebuild:
			_fen_tree = self._fen_tree
			while index < len(_fen_tree):
				_fen_tree[index] += value
				index |= index + 1

	def _fen_query(self, end):
		if self._rebuild:
			self._fen_build()
		_fen_tree = self._fen_tree
		x = 0
		while end:
			x += _fen_tree[end - 1]
			end &= end - 1
		return x

	def _fen_findkth(self, k):
		_list_lens = self._list_lens
		if k < _list_lens[0]:
			return (0, k)
		if k >= self._len - _list_lens[-1]:
			return (len(_list_lens) - 1, k + _list_lens[-1] - self._len)
		if self._rebuild:
			self._fen_build()
		_fen_tree = self._fen_tree
		idx = -1
		for d in reversed(range(len(_fen_tree).bit_length())):
			right_idx = idx + (1 << d)
			if right_idx < len(_fen_tree) and k >= _fen_tree[right_idx]:
				idx = right_idx
				k -= _fen_tree[idx]
		return (idx + 1, k)

	def _delete(self, pos, idx):
		_lists = self._lists
		_mins = self._mins
		_list_lens = self._list_lens
		self._len -= 1
		self._fen_update(pos, -1)
		del _lists[pos][idx]
		_list_lens[pos] -= 1
		if _list_lens[pos]:
			_mins[pos] = _lists[pos][0]
		else:
			del _lists[pos]
			del _list_lens[pos]
			del _mins[pos]
			self._rebuild = True

	def _loc_left(self, value):
		if not self._len:
			return (0, 0)
		_lists = self._lists
		_mins = self._mins
		(lo, pos) = (-1, len(_lists) - 1)
		while lo + 1 < pos:
			mi = lo + pos >> 1
			if value <= _mins[mi]:
				pos = mi
			else:
				lo = mi
		if pos and value <= _lists[pos - 1][-1]:
			pos -= 1
		_list = _lists[pos]
		(lo, idx) = (-1, len(_list))
		while lo + 1 < idx:
			mi = lo + idx >> 1
			if value <= _list[mi]:
				idx = mi
			else:
				lo = mi
		return (pos, idx)

	def _loc_right(self, value):
		if not self._len:
			return (0, 0)
		_lists = self._lists
		_mins = self._mins
		(pos, hi) = (0, len(_lists))
		while pos + 1 < hi:
			mi = pos + hi >> 1
			if value < _mins[mi]:
				hi = mi
			else:
				pos = mi
		_list = _lists[pos]
		(lo, idx) = (-1, len(_list))
		while lo + 1 < idx:
			mi = lo + idx >> 1
			if value < _list[mi]:
				idx = mi
			else:
				lo = mi
		return (pos, idx)

	def add(self, value):
		_load = self._load
		_lists = self._lists
		_mins = self._mins
		_list_lens = self._list_lens
		self._len += 1
		if _lists:
			(pos, idx) = self._loc_right(value)
			self._fen_update(pos, 1)
			_list = _lists[pos]
			_list.insert(idx, value)
			_list_lens[pos] += 1
			_mins[pos] = _list[0]
			if _load + _load < len(_list):
				_lists.insert(pos + 1, _list[_load:])
				_list_lens.insert(pos + 1, len(_list) - _load)
				_mins.insert(pos + 1, _list[_load])
				_list_lens[pos] = _load
				del _list[_load:]
				self._rebuild = True
		else:
			_lists.append([value])
			_mins.append(value)
			_list_lens.append(1)
			self._rebuild = True

	def discard(self, value):
		_lists = self._lists
		if _lists:
			(pos, idx) = self._loc_right(value)
			if idx and _lists[pos][idx - 1] == value:
				self._delete(pos, idx - 1)

	def remove(self, value):
		_len = self._len
		self.discard(value)
		if _len == self._len:
			raise ValueError('{0!r} not in list'.format(value))

	def pop(self, index=-1):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		value = self._lists[pos][idx]
		self._delete(pos, idx)
		return value

	def bisect_left(self, value):
		(pos, idx) = self._loc_left(value)
		return self._fen_query(pos) + idx

	def bisect_right(self, value):
		(pos, idx) = self._loc_right(value)
		return self._fen_query(pos) + idx

	def count(self, value):
		return self.bisect_right(value) - self.bisect_left(value)

	def __len__(self):
		return self._len

	def __getitem__(self, index):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		return self._lists[pos][idx]

	def __delitem__(self, index):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		self._delete(pos, idx)

	def __contains__(self, value):
		_lists = self._lists
		if _lists:
			(pos, idx) = self._loc_left(value)
			return idx < len(_lists[pos]) and _lists[pos][idx] == value
		return False

	def __iter__(self):
		return (value for _list in self._lists for value in _list)

	def __reversed__(self):
		return (value for _list in reversed(self._lists) for value in reversed(_list))

	def __repr__(self):
		return 'SortedList({0})'.format(list(self))

class SegTree:

	def __init__(self, n):
		self.N = 1 << n.bit_length()
		self.tree = [0] * (self.N << 1)

	def update(self, i, j, v):
		i += self.N
		j += self.N
		while i <= j:
			if i % 2 == 1:
				self.tree[i] += v
			if j % 2 == 0:
				self.tree[j] += v
			(i, j) = (i + 1 >> 1, j - 1 >> 1)

	def query(self, i):
		v = 0
		i += self.N
		while i > 0:
			v += self.tree[i]
			i >>= 1
		return v

def SieveOfEratosthenes(limit):
	isPrime = [True] * (limit + 1)
	isPrime[0] = isPrime[1] = False
	primes = []
	for i in range(2, limit + 1):
		if not isPrime[i]:
			continue
		primes += [i]
		for j in range(i * i, limit + 1, i):
			isPrime[j] = False
	return primes
from collections import Counter

def gcd(x, y):
	while y:
		(x, y) = (y, x % y)
	return x

def memodict(f):

	class memodict(dict):

		def __missing__(self, key):
			ret = self[key] = f(key)
			return ret
	return memodict().__getitem__

def pollard_rho(n):
	if n & 1 == 0:
		return 2
	if n % 3 == 0:
		return 3
	s = (n - 1 & 1 - n).bit_length() - 1
	d = n >> s
	for a in [2, 325, 9375, 28178, 450775, 9780504, 1795265022]:
		p = pow(a, d, n)
		if p == 1 or p == n - 1 or a % n == 0:
			continue
		for _ in range(s):
			prev = p
			p = p * p % n
			if p == 1:
				return gcd(prev - 1, n)
			if p == n - 1:
				break
		else:
			for i in range(2, n):
				(x, y) = (i, (i * i + 1) % n)
				f = gcd(abs(x - y), n)
				while f == 1:
					(x, y) = ((x * x + 1) % n, (y * y + 1) % n)
					y = (y * y + 1) % n
					f = gcd(abs(x - y), n)
				if f != n:
					return f
	return n

@memodict
def prime_factors(n):
	if n <= 1:
		return Counter()
	f = pollard_rho(n)
	return Counter([n]) if f == n else prime_factors(f) + prime_factors(n // f)

def distinct_factors(n):
	factors = [1]
	for (p, exp) in prime_factors(n).items():
		factors += [p ** i * factor for factor in factors for i in range(1, exp + 1)]
	return factors

def all_factors(n):
	(small, large) = ([], [])
	for i in range(1, int(n ** 0.5) + 1, 2 if n & 1 else 1):
		if not n % i:
			small.append(i)
			large.append(n // i)
	if small[-1] == large[-1]:
		large.pop()
	large.reverse()
	small.extend(large)
	return small
	return ans

def main():
	mod = 1000000007
	starttime = datetime.datetime.now()
	if os.path.exists('input.txt'):
		sys.stdin = open('input.txt', 'r')
		sys.stdout = open('output.txt', 'w')
	tc = 1
	tc = ri()
	for _ in range(tc):
		n = ri()
		a = ria()
		m = ri()
		endurances = [0] * (n + 1)
		for i in range(m):
			(power, endurance) = ria()
			endurances[endurance] = max(power, endurances[endurance])
		for i in range(n - 1, 0, -1):
			endurances[i] = max(endurances[i], endurances[i + 1])
		flag = 0
		ans = 1
		count = 1
		currmax = a[0]
		for i in a:
			currmax = max(i, currmax)
			if endurances[count] >= currmax:
				count += 1
			else:
				ans += 1
				count = 1
				currmax = i
				if endurances[count] < i:
					flag = 1
					break
				else:
					count += 1
		if flag:
			wi(-1)
		else:
			wi(ans)
	endtime = datetime.datetime.now()
	time = (endtime - starttime).total_seconds() * 1000
	if os.path.exists('input.txt'):
		print('Time:', time, 'ms')

class FastReader(io.IOBase):
	newlines = 0

	def __init__(self, fd, chunk_size=1024 * 8):
		self._fd = fd
		self._chunk_size = chunk_size
		self.buffer = io.BytesIO()

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, self._chunk_size))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self, size=-1):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, self._chunk_size if size == -1 else size))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

class FastWriter(io.IOBase):

	def __init__(self, fd):
		self._fd = fd
		self.buffer = io.BytesIO()
		self.write = self.buffer.write

	def flush(self):
		os.write(self._fd, self.buffer.getvalue())
		(self.buffer.truncate(0), self.buffer.seek(0))

class FastStdin(io.IOBase):

	def __init__(self, fd=0):
		self.buffer = FastReader(fd)
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

class FastStdout(io.IOBase):

	def __init__(self, fd=1):
		self.buffer = FastWriter(fd)
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.flush = self.buffer.flush
sys.stdin = FastStdin()
sys.stdout = FastStdout()
main()


from bisect import bisect_left as bl, bisect_right as br, insort
import sys
import heapq
from math import *
from collections import defaultdict as dd, deque

def data():
	return sys.stdin.readline().strip()

def mdata():
	return map(int, data().split())
mod = int(1000000000.0 + 7)
for t in range(int(data())):
	(n,) = mdata()
	A = list(mdata())
	(m,) = mdata()
	d = dd(int)
	for i in range(m):
		(a, b) = mdata()
		d[b] = max(d[b], a)
	dp = [0] * n
	max1 = 0
	for i in range(n):
		dp[n - i - 1] = max(d[n - i], max1)
		max1 = dp[n - i - 1]
	cnt = 1
	ind = 0
	i = 0
	max1 = 0
	while i < n:
		max1 = max(max1, A[i])
		if max1 > dp[0]:
			cnt = -1
			break
		elif max1 <= dp[ind]:
			ind += 1
		else:
			cnt += 1
			ind = 0
			max1 = 0
			i -= 1
		i += 1
	print(cnt)


cases = int(input())
for c in range(cases):
	n_monsters = int(input())
	powers_mons = [int(x) for x in input().split()]
	heroes = int(input())
	hero_power = []
	hero_endurance = []
	for i in range(heroes):
		(x, y) = map(int, input().split())
		hero_power.append(x)
		hero_endurance.append(y)
	bst = [0 for i in range(n_monsters + 1)]
	for i in range(heroes):
		bst[hero_endurance[i]] = max(bst[hero_endurance[i]], hero_power[i])
	for i in range(n_monsters - 1, -1, -1):
		bst[i] = max(bst[i + 1], bst[i])
	x = 0
	cnt = 0
	mst = 0
	while mst != n_monsters:
		prev = mst
		m_p = powers_mons[mst]
		x = 1
		while m_p <= bst[x]:
			x += 1
			mst += 1
			if mst == n_monsters:
				break
			m_p = max(m_p, powers_mons[mst])
		if mst == prev:
			cnt = -1
			break
		cnt += 1
	print(cnt)


import bisect
import sys
input = sys.stdin.readline
for _ in range(int(input())):
	n = int(input())
	ar = list(map(int, input().split()))
	m = int(input())
	po = []
	for i in range(m):
		po.append(list(map(int, input().split())))
	po.sort(key=lambda x: x[0])
	en = [0] * m
	powd = []
	ma = 0
	for i in range(1, m + 1):
		powd.append(po[i - 1][0])
		ma = max(ma, po[-i][1])
		en[-i] = ma
	if max(ar) > max(powd):
		print(-1)
	else:
		ans = 1
		count = 0
		prev = bisect.bisect_left(powd, ar[0])
		for i in range(n):
			xx = bisect.bisect_left(powd, ar[i])
			if xx >= prev:
				prev = xx
			if en[prev] >= count + 1:
				count += 1
			else:
				if xx < prev:
					prev = xx
				count = 1
				ans += 1
		print(ans)


import sys
input = sys.stdin.readline
from bisect import *
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	m = int(input())
	ps = [tuple(map(int, input().split())) for _ in range(m)]
	ps.sort(key=lambda k: k[0], reverse=True)
	(p, s) = ([], [])
	s_max = 0
	for (pi, si) in ps:
		if si > s_max:
			p.append(pi)
			s.append(si)
			s_max = si
	(p, s) = (p[::-1], s[::-1])
	if max(a) > p[-1]:
		print(-1)
		continue
	i = 0
	defeated = 0
	ans = 1
	prev_idx = -1
	while i < n:
		idx = bisect_left(p, a[i])
		idx = max(prev_idx, idx)
		if defeated < s[idx]:
			i += 1
			defeated += 1
			prev_idx = idx
		else:
			defeated = 0
			ans += 1
			prev_idx = -1
	print(ans)


def main():
	t = int(input())
	for q in range(t):
		n = int(input())
		a = list(map(int, input().split()))
		a = [0] + a
		m = int(input())
		b = [0] * (n + 1)
		for i in range(0, m):
			(p, s) = map(int, input().split())
			b[s] = max(b[s], p)
		for i in range(n - 1, -1, -1):
			b[i] = max(b[i], b[i + 1])
		ans = 0
		k = 0
		while k < n:
			q = 0
			t = 0
			while k + t + 1 <= n and b[t + 1] >= max(q, a[k + t + 1]):
				q = max(q, a[k + t + 1])
				t += 1
			if t == 0:
				ans = -1
				break
			k += t
			ans += 1
		print(ans)
main()


import math
from collections import Counter
import math
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	m = int(input())
	d = [0] * (n + 1)
	for i in range(m):
		(u, v) = map(int, input().split())
		d[v] = max(d[v], u)
	for i in range(n - 1, -1, -1):
		d[i] = max(d[i], d[i + 1])
	ans = 1
	cnt = 1
	ma = 0
	if d[1] < max(arr):
		ans = -1
	else:
		for i in arr:
			ma = max(ma, i)
			if d[cnt] < ma:
				cnt = 1
				ans += 1
				ma = i
			cnt += 1
	print(ans)


import os, sys, bisect, copy
from collections import defaultdict, Counter, deque
from functools import lru_cache
if os.path.exists('in.txt'):
	sys.stdin = open('in.txt', 'r')
if os.path.exists('out.txt'):
	sys.stdout = open('out.txt', 'w')

def input():
	return sys.stdin.readline()

def mapi(arg=0):
	return map(int if arg == 0 else str, input().split())
for _ in range(int(input())):
	n = int(input())
	a = list(mapi())
	m = int(input())
	heroes = []
	mxp = defaultdict(int)
	for i in range(m):
		(p, s) = mapi()
		heroes.append([p, s])
		mxp[s] = max(mxp[s], p)
	for i in range(n - 1, -1, -1):
		mxp[i] = max(mxp[i + 1], mxp[i])
	if mxp[0] < max(a):
		print(-1)
		continue
	res = 0
	cnt = 0
	mx = 0
	for x in a:
		cnt += 1
		mx = max(mx, x)
		if mxp[cnt] < mx:
			res += 1
			mx = x
			cnt = 1
	if cnt > 0:
		res += 1
	print(res)


def main():
	t = int(input())
	allans = []
	for _ in range(t):
		n = int(input())
		a = readIntArr()
		m = int(input())
		ps = []
		for __ in range(m):
			ps.append(readIntArr())
		maxMonsterPower = max(a)
		maxHeroPower = 0
		for (p, s) in ps:
			maxHeroPower = max(maxHeroPower, p)
		if maxMonsterPower > maxHeroPower:
			allans.append(-1)
			continue
		maxPower = [-1 for _ in range(n + 1)]
		for (p, s) in ps:
			maxPower[s] = max(maxPower[s], p)
		for i in range(n - 1, -1, -1):
			maxPower[i] = max(maxPower[i], maxPower[i + 1])
		currMonst = 0
		nDays = 0
		while currMonst < n:
			nDays += 1
			nextMonst = currMonst
			monstMax = a[nextMonst]
			for nMonst in range(1, n + 1):
				if maxPower[nMonst] < monstMax:
					assert nMonst != 1
					break
				nextMonst += 1
				if nextMonst == n:
					break
				monstMax = max(monstMax, a[nextMonst])
			assert nextMonst > currMonst
			currMonst = nextMonst
		allans.append(nDays)
	multiLineArrayPrint(allans)
	return
import sys
input = sys.stdin.buffer.readline

def oneLineArrayPrint(arr):
	print(' '.join([str(x) for x in arr]))

def multiLineArrayPrint(arr):
	print('\n'.join([str(x) for x in arr]))

def multiLineArrayOfArraysPrint(arr):
	print('\n'.join([' '.join([str(x) for x in y]) for y in arr]))

def readIntArr():
	return [int(x) for x in input().split()]

def makeArr(defaultVal, dimensionArr):
	dv = defaultVal
	da = dimensionArr
	if len(da) == 1:
		return [dv for _ in range(da[0])]
	else:
		return [makeArr(dv, da[1:]) for _ in range(da[0])]

def queryInteractive(x, y):
	print('? {} {}'.format(x, y))
	sys.stdout.flush()
	return int(input())

def answerInteractive(ans):
	print('! {}'.format(ans))
	sys.stdout.flush()
inf = float('inf')
MOD = 10 ** 9 + 7
for _abc in range(1):
	main()


from collections import *
from bisect import bisect_left as bl
import sys
input = sys.stdin.readline

def li():
	return [int(i) for i in input().rstrip('\n').split(' ')]

def st():
	return input().rstrip('\n')

def val():
	return int(input())

def stli():
	return [int(i) for i in input().rstrip('\n')]
for _ in range(val()):
	n = val()
	a = li()
	m = val()
	h = []
	visited = defaultdict(int)
	for i in range(m):
		(x, y) = li()
		visited[x] = max(visited[x], y)
	h = []
	for i in visited:
		h.append([i, visited[i]])
	h.sort(reverse=1)
	endurance = {}
	m = len(h)
	currmax = -float('inf')
	for i in range(m):
		if h[i][1] > currmax:
			currmax = max(currmax, h[i][1])
			endurance[h[i][0]] = currmax
	power = sorted(list(endurance))
	totdays = 0
	i = 0
	while i < n:
		ind = bl(power, a[i])
		if ind == len(power):
			totdays = -1
			break
		cou = 0
		while i < n:
			while ind < len(power) and a[i] > power[ind]:
				ind += 1
			if ind == len(power):
				totdays = -1
				break
			if endurance[power[ind]] <= cou:
				break
			i += 1
			cou += 1
		if totdays == -1:
			break
		totdays += 1
	print(totdays)


import sys
input = sys.stdin.readline

class RangeMinimumQuery:

	def __init__(self, n, func=min, inf=float('inf')):
		self.n0 = 2 ** (n - 1).bit_length()
		self.op = func
		self.inf = inf
		self.data = [self.inf] * (2 * self.n0 - 1)

	def query(self, l, r):
		l += self.n0
		r += self.n0
		res = self.inf
		while l < r:
			if r & 1:
				r -= 1
				res = self.op(res, self.data[r - 1])
			if l & 1:
				res = self.op(res, self.data[l - 1])
				l += 1
			l >>= 1
			r >>= 1
		return res

	def update(self, i, x):
		i += self.n0 - 1
		self.data[i] = x
		while i + 1:
			i = ~-i // 2
			self.data[i] = self.op(self.data[2 * i + 1], self.data[2 * i + 2])

def solve():
	n = int(input())
	a = list(map(int, input().split()))
	RMQ = RangeMinimumQuery(n, func=max, inf=0)
	for (i, ai) in enumerate(a):
		RMQ.update(i, ai)
	m = int(input())
	ps = [list(map(int, input().split())) for i in range(m)]
	bst = [0] * (n + 1)
	for (p, s) in ps:
		bst[s] = max(bst[s], p)
	for i in reversed(range(1, n + 1)):
		bst[i - 1] = max(bst[i - 1], bst[i])
	cur = -1
	ans = 0
	while cur != n - 1:
		left = cur
		right = n
		while right - left > 1:
			mid = (right + left) // 2
			x = mid - cur
			if RMQ.query(cur + 1, mid + 1) > bst[x]:
				right = mid
			else:
				left = mid
		if left == cur:
			print(-1)
			return
		cur = left
		ans += 1
	print(ans)
t = int(input())
for i in range(t):
	solve()


import os
import sys
from collections import defaultdict
from io import BytesIO, IOBase
nmbr = lambda : int(input())
lst = lambda : list(map(int, input().split()))

def main():
	for _ in range(nmbr()):
		PI = float('inf')
		n = nmbr()
		a = lst()
		end = defaultdict(int)
		nh = nmbr()
		N = 1
		for i in range(nh):
			(power, endurance) = lst()
			end[endurance] = max(end[endurance], power)
			N = max(endurance, N)
		for i in range(N - 1, 0, -1):
			end[i] = max(end[i], end[i + 1])
		(x, f) = (0, 1)
		ans = 0
		while x < n:
			mx = 0
			taken = 0
			for i in range(x, n):
				mx = max(mx, a[i])
				if mx <= end[taken + 1]:
					taken += 1
				else:
					break
			if taken == 0:
				f = 0
				break
			else:
				ans += 1
				x = x + taken
		print(ans if f else -1)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
for t in range(1):
	main()


import sys
input = lambda : sys.stdin.readline().strip()
print = lambda s: sys.stdout.write(s)
t = int(input())
for i in range(t):
	n = int(input())
	ls1 = list(map(int, input().split()))
	m = int(input())
	ls2 = []
	for i in range(m):
		ls2.append(tuple(map(int, input().split())))
	if max(ls1) > max((i[0] for i in ls2)):
		print('-1\n')
	else:
		temp = {}
		for i in range(1, n + 1):
			temp[i] = 0
		for i in ls2:
			try:
				temp[i[1]] = max(temp[i[1]], i[0])
			except:
				temp[i[1]] = i[0]
		d = {}
		d[n] = temp[n]
		for k in range(n - 1, 0, -1):
			d[k] = max(d[k + 1], temp[k])
		i = 0
		cnt = 1
		ans = 1
		M = ls1[0]
		while True:
			if d[cnt] >= M:
				cnt += 1
				i += 1
				if i == n:
					break
				M = max(M, ls1[i])
			else:
				ans += 1
				cnt = 1
				M = ls1[i]
		print(str(ans) + '\n')


q = int(input())
for i in range(q):
	n = int(input())
	a = input().split(' ')
	a = [int(a[k]) for k in range(n)]
	m = int(input())
	p = list()
	s = list()
	dp = [0 for j in range(n + 1)]
	for j in range(m):
		l = input().split(' ')
		l = [int(l[k]) for k in range(0, 2)]
		p.append(l[0])
		s.append(l[1])
		dp[l[1]] = max(dp[l[1]], l[0])
	for j in range(n - 1, 0, -1):
		dp[j] = max(dp[j], dp[j + 1])
	zi = 0
	ok = True
	ans = 0
	while zi < n and ok == True:
		ans += 1
		curr = zi
		maxp = a[curr]
		while maxp <= dp[curr - zi + 1]:
			curr += 1
			if curr == n:
				break
			maxp = max(maxp, a[curr])
		if curr == zi:
			ok = False
		zi = curr
	if ok == True:
		print(ans)
	else:
		print('-1')


T = int(input())
for t in range(T):
	N = int(input())
	A = list(map(int, input().split()))
	M = int(input())
	heroes = []
	for m in range(M):
		hero = list(map(int, input().split()))
		heroes.append(hero)
	best = {}
	for (p, s) in heroes:
		best[s] = max(best.get(s, 0), p)
	for i in range(N - 1, -1, -1):
		best[i] = max(best.get(i, 0), best.get(i + 1, 0))
	cnt = 0
	res = 0
	while cnt < N:
		if A[cnt] > best[1]:
			res = -1
			break
		else:
			x = 0
			i = cnt + x
			maxa = A[i]
			while i < N:
				maxa = max(maxa, A[i])
				if maxa > best.get(x + 1, 0):
					x -= 1
					i -= 1
					break
				x += 1
				i = cnt + x
			res += 1
			cnt += x + 1
	print(res)


import sys
import math
from collections import defaultdict, Counter, deque
import bisect
import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	m = int(input())
	l = []
	for j in range(m):
		(p, s) = map(int, input().split())
		l.append([p, s])
	pre = {}
	l.sort()
	cur = [0, 0]
	for j in range(m - 1, -1, -1):
		if l[j][1] > cur[0]:
			cur = [l[j][1], j]
		pre[l[j][0]] = cur
	start = 0
	ind = cur[1]
	ans = 0
	for j in range(n):
		if a[j] > l[ind][0]:
			ind = bisect.bisect_left(l, [a[j], 0])
			if ind == m:
				ans = -2
				break
			ind = pre[l[ind][0]][1]
			if l[ind][1] < j - start + 1:
				ans += 1
				start = j
		if j - start + 1 == l[ind][1]:
			ans += 1
			start = j + 1
			ind = cur[1]
	if start != n:
		ans += 1
	print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	s = [int(x) for x in input().split()]
	m = int(input())
	L = []
	for i in range(m):
		(pi, si) = map(int, input().split())
		L.append((pi, si))
	edu = [0] * (n + 1)
	for i in range(0, len(L)):
		edu[L[i][1]] = max(edu[L[i][1]], L[i][0])
	mx = edu[n]
	opt = [edu[n]]
	for i in range(n - 1, -1, -1):
		mx = max(mx, edu[i])
		opt.append(mx)
	opt = opt[::-1]
	if max(opt) < max(s):
		print(-1)
	else:
		temp = -1
		ptr = 0
		curr_mx = 0
		ct = 0
		ans = 1
		while ptr < n:
			curr_mx = max(curr_mx, s[ptr])
			if opt[ct + 1] >= curr_mx:
				ptr += 1
				ct += 1
			else:
				ans += 1
				curr_mx = 0
				ct = 0
		print(ans)


import math, sys
from collections import Counter, defaultdict, deque
from sys import stdin, stdout
input = stdin.readline
lili = lambda : list(map(int, sys.stdin.readlines()))
li = lambda : list(map(int, input().split()))
I = lambda : int(input())
S = lambda : input()
t = I()
while t:
	n = I()
	a = li()
	m = I()
	b = [0] * (n + 2)
	c = []
	for i in range(0, m):
		c.append(li())
		b[c[i][1]] = max(b[c[i][1]], c[i][0])
	for i in range(n - 1, -1, -1):
		b[i] = max(b[i], b[i + 1])
	pos = 0
	res = 0
	ok = True
	while pos < n:
		res += 1
		npos = pos
		mx = 0
		while npos < n:
			mx = max(mx, a[npos])
			if mx > b[npos - pos + 1]:
				break
			npos += 1
		if pos == npos:
			ok = False
			break
		pos = npos
	if not ok:
		res = -1
	print(res)
	t -= 1


import sys

def I():
	return sys.stdin.readline().rstrip()
for _ in range(int(I())):
	n = int(I())
	a = list(map(int, I().split()))
	m = int(I())
	pl = sorted([list(map(int, I().split())) for _ in range(m)])
	(pln, mxs) = ([], 0)
	for x in pl[::-1]:
		if x[1] > mxs:
			pln.append(x)
		mxs = max(mxs, x[1])
	pl = pln[::-1]
	m = len(pl)
	(p, s) = map(list, zip(*pl))
	if max(a) > max(p):
		print(-1)
	else:
		days = 0
		c = 0
		d2 = 1
		while d2 <= m:
			d2 *= 2
		d2 //= 2
		while c < n:
			days += 1
			mx = 0
			inday = 0
			while c < n:
				mx = max(mx, a[c])
				inday += 1
				pi = -1
				d = d2
				while d:
					np = pi + d
					if np < m and p[np] < mx:
						pi = np
					d //= 2
				pi += 1
				if pi < m and s[pi] >= inday:
					c += 1
				else:
					break
		print(days)


from sys import stdin

def iin():
	return int(stdin.readline())

def lin():
	return list(map(int, stdin.readline().split()))

def main():
	t = iin()
	while t:
		t -= 1
		n = iin()
		a = lin()
		m = iin()
		h = [lin()[::-1] for i in range(m)]
		h.sort(reverse=True)
		a1 = [[j, i] for (i, j) in enumerate(a)]
		a2 = [-1] * n
		a1.sort()
		i = 0
		j = 0
		while j < n and i < m:
			if h[i][1] >= a1[j][0]:
				a2[a1[j][1]] = i
				j += 1
			else:
				i += 1
		if -1 in a2:
			print(-1)
		else:
			dp = [1] * n
			for i in range(1, n):
				ad = [0]
				ch = 0
				if h[a2[i]][0] > dp[i - 1]:
					if h[a2[i]][1] >= h[a2[i - 1]][1]:
						ad.append(dp[i - 1])
						ch += 1
				if h[a2[i - 1]][0] > dp[i - 1]:
					if h[a2[i - 1]][1] >= h[a2[i]][1]:
						ad.append(dp[i - 1])
						if ch == 0:
							a2[i] = a2[i - 1]
				dp[i] += max(ad)
			print(dp.count(1))
main()


import sys
input = sys.stdin.readline
for nt in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	m = int(input())
	maxx = {}
	for i in range(m):
		(a, b) = map(int, input().split())
		if b not in maxx:
			maxx[b] = a
		else:
			maxx[b] = max(a, maxx[b])
	arr = []
	for i in maxx:
		arr.append([maxx[i], i])
	arr.sort(reverse=True)
	pref = []
	prev = 0
	for i in range(len(arr)):
		new = arr[i][1]
		if new > prev:
			for j in range(prev, new):
				pref.append(arr[i][0])
			prev = new
	if pref[0] < max(l):
		print(-1)
		continue
	m = 0
	count = 0
	day = 0
	for i in range(n):
		m = max(m, l[i])
		count += 1
		if count > len(pref) or pref[count - 1] < m:
			day += 1
			count = 1
			m = l[i]
	print(day + 1)


t = int(input())
for ij in range(0, t):
	n = int(input())
	a = [0] + list(map(int, input().split()))
	m = int(input())
	l = [0] * (n + 1)
	for i in range(0, m):
		(p, s) = map(int, input().split())
		l[s] = max(l[s], p)
	for i in range(n - 1, -1, -1):
		l[i] = max(l[i], l[i + 1])
	ans = 0
	k = 0
	while k < n:
		q = 0
		t = 0
		while k + t + 1 <= n and l[t + 1] >= max(q, a[k + t + 1]):
			q = max(q, a[k + t + 1])
			t += 1
		if t == 0:
			ans = -1
			break
		k += t
		ans += 1
	print(ans)


import os
import sys

def main():
	T = read_int()
	for _ in range(T):
		N = read_int()
		A = read_ints()
		M = read_int()
		H = [tuple(read_ints()) for _ in range(M)]
		print(solve(N, A, M, H))

def solve(N, A, M, H):
	H.sort(key=lambda h: (h[1], -h[0]))
	spow = [0] * (N + 1)
	s0 = 0
	for (p, s) in H:
		if s0 == s:
			continue
		spow[s] = p
		s0 = s
	maxp = 0
	for d in range(N, -1, -1):
		maxp = max(maxp, spow[d])
		spow[d] = maxp
	ans = 0
	maxa = A[0]
	if A[0] > spow[1]:
		return -1
	start = 0
	for (i, a) in enumerate(A[1:]):
		if a > spow[1]:
			return -1
		i += 1
		days = i - start + 1
		maxa = max(maxa, a)
		if spow[days] < maxa:
			ans += 1
			maxa = a
			start = i
	return ans + 1
DEBUG = 'DEBUG' in os.environ

def inp():
	return sys.stdin.readline().rstrip()

def read_int():
	return int(inp())

def read_ints():
	return [int(e) for e in inp().split()]

def dprint(*value, sep=' ', end='\n'):
	if DEBUG:
		print(*value, sep=sep, end=end)
main()


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	n = int(input())
	mons = tuple(map(int, input().split()))
	m = int(input())
	_heros = sorted((tuple(map(int, input().split())) for _ in range(m)), reverse=True) + [(0, 10 ** 9)]
	heros = []
	max_s = 0
	for i in range(m + 1):
		if _heros[i][1] <= max_s:
			continue
		heros.append(_heros[i])
		max_s = max(max_s, _heros[i][1])
	if heros[0][0] < max(mons):
		print(-1)
		continue
	mons_i = 0
	for ans in range(1, 10 ** 9):
		hero_i = 0
		max_mons_power = 0
		for i in range(n - mons_i):
			while heros[hero_i][1] <= i:
				hero_i += 1
			max_mons_power = max(max_mons_power, mons[mons_i])
			if heros[hero_i][0] < max_mons_power:
				break
			mons_i += 1
		else:
			print(ans)
			break


def main():
	print = out.append
	n = get_int()
	monsters = get_list()
	m = get_int()
	heros = [get_list() for _ in range(m)]
	heros.append([0, 10 ** 10])
	heros.append([0, 0])
	heros.sort(key=lambda x: x[1], reverse=True)
	endu = [0] * (n + 1)
	ptr = 0
	max_power = 0
	for i in range(n, 0, -1):
		while heros[ptr + 1][1] >= i:
			ptr += 1
			max_power = max(max_power, heros[ptr][0])
		endu[i] = max_power
	ptr = res = base = 0
	while base != n:
		res += 1
		max_mon = monsters[ptr]
		while ptr < n and endu[ptr - base + 1] >= max_mon:
			ptr += 1
			max_mon = max(monsters[ptr], max_mon) if ptr < n else max_mon
		if base == ptr:
			print(-1)
			return
		base = ptr
	print(res)
import sys
from collections import defaultdict
input = iter(sys.stdin.buffer.read().decode().splitlines()).__next__
out = []
get_int = lambda : int(input())
get_list = lambda : list(map(int, input().split()))
[main() for _ in range(int(input()))]
print(*out, sep='\n')


from bisect import bisect_left, bisect_right
import sys

def input():
	return sys.stdin.readline().rstrip()

class SegTree:

	def __init__(self, N, function, basement):
		self.n = N
		self.K = (self.n - 1).bit_length()
		self.f = function
		self.b = basement
		self.X = 1 << self.K
		self.seg = [basement] * (2 * self.X + 1)
		for i in range(self.X - 1, 0, -1):
			self.seg[i] = self.f(self.seg[i << 1], self.seg[i << 1 | 1])

	def all_update(self, LISTS):
		m = len(LISTS)
		assert m < self.n
		for (i, v) in enumerate(LISTS):
			self.seg[i + self.X] = v
		for i in range(self.X - 1, 0, -1):
			self.seg[i] = self.f(self.seg[i << 1], self.seg[i << 1 | 1])

	def update(self, k, value):
		X = self.X
		k += X
		self.seg[k] = value
		while k:
			k = k >> 1
			self.seg[k] = self.f(self.seg[k << 1], self.seg[k << 1 | 1])

	def query(self, L, R):
		num = self.X
		L += num
		R += num
		vL = self.b
		vR = self.b
		while L < R:
			if L & 1:
				vL = self.f(vL, self.seg[L])
				L += 1
			if R & 1:
				R -= 1
				vR = self.f(self.seg[R], vR)
			L >>= 1
			R >>= 1
		return self.f(vL, vR)

	def get(self, idx):
		assert idx < self.n
		return self.query(idx, idx + 1)

def slv():
	monster_n = int(input())
	monsters = list(map(int, input().split()))
	hero_n = int(input())
	heros = [tuple(map(int, input().split())) for i in range(hero_n)]
	Q = SegTree(monster_n + 100, max, 0)
	Q.all_update(monsters)
	heros.sort(key=lambda x: x[0])
	heros_strength = [heros[i][0] for i in range(hero_n)]
	heros_endure = [0] + [heros[i][1] for i in range(hero_n)][::-1]
	for i in range(1, hero_n + 1):
		heros_endure[i] = max(heros_endure[i], heros_endure[i - 1])

	def possible(delete_count, now_idx):
		strongest_monster = Q.query(now_idx, min(now_idx + delete_count, monster_n))
		can_compete = hero_n - bisect_left(heros_strength, strongest_monster)
		return heros_endure[can_compete] >= delete_count
	ans = 0
	idx = 0
	while idx < monster_n:
		l = 0
		r = monster_n + 1
		while r - l > 1:
			med = (r + l) // 2
			if possible(med, idx):
				l = med
			else:
				r = med
		if l == 0:
			print(-1)
			return
		idx += l
		ans += 1
	print(ans)
	return

def main():
	t = int(input())
	for i in range(t):
		slv()
	return
main()


t = int(input())
for r in range(0, t):
	n = int(input())
	a = list(map(int, input().split()))
	monster = max(a)
	m = int(input())
	h = list((tuple(map(int, input().split())) for i in range(m)))
	h.sort()
	if monster > h[m - 1][0]:
		print(-1)
		continue
	i = m - 2
	last = h[m - 1][1]
	while i >= 0:
		if h[i][1] <= last:
			del h[i]
		else:
			last = h[i][1]
		i -= 1
	index = 0
	ans = 0
	size = len(h) - 1
	while index < n:
		mx = a[index]
		s = h[size][1]
		i = size
		while h[i][0] >= mx and index < n:
			if s != 0:
				index += 1
				if index == n:
					break
				mx = max(a[index], mx)
				s -= 1
			else:
				if i == 0:
					break
				s = h[i - 1][1] - h[i][1]
				i -= 1
		ans += 1
	print(ans)


import sys
input = sys.stdin.readline

def init_max(init_max_val):
	for i in range(n):
		seg_max[i + num_max - 1] = init_max_val[i]
	for i in range(num_max - 2, -1, -1):
		seg_max[i] = max(seg_max[2 * i + 1], seg_max[2 * i + 2])

def update_max(k, x):
	k += num_max - 1
	seg_max[k] = x
	while k:
		k = (k - 1) // 2
		seg_max[k] = max(seg_max[k * 2 + 1], seg_max[k * 2 + 2])

def query_max(p, q):
	if q <= p:
		return ide_ele_max
	p += num_max - 1
	q += num_max - 2
	res = ide_ele_max
	while q - p > 1:
		if p & 1 == 0:
			res = max(res, seg_max[p])
		if q & 1 == 1:
			res = max(res, seg_max[q])
			q -= 1
		p = p // 2
		q = (q - 1) // 2
	if p == q:
		res = max(res, seg_max[p])
	else:
		res = max(max(res, seg_max[p]), seg_max[q])
	return res
qq = int(input())
for testcases in [0] * qq:
	n = int(input())
	a = list(map(int, input().split()))
	m = int(input())
	p = [-1] * n
	for _ in [0] * m:
		(x, y) = map(int, input().split())
		p[y - 1] = max(p[y - 1], x)
	tmp_max = -1
	for i in range(n - 1, -1, -1):
		tmp_max = max(tmp_max, p[i])
		p[i] = tmp_max
	if p[0] < max(a):
		print(-1)
		continue
	if n == 1:
		print(1)
		continue
	if n == 2:
		if p[1] >= a[0] and p[1] >= a[1]:
			print(1)
		else:
			print(2)
		continue
	ide_ele_max = -1
	num_max = 2 ** (n - 1).bit_length()
	seg_max = [ide_ele_max] * 2 * num_max
	init_max(a)
	start = 0
	res = 0
	while start < n:
		ok = 0
		ng = n - start
		while ng - ok > 1:
			mid = (ok + ng) // 2
			if query_max(start, start + mid + 1) <= p[mid]:
				ok = mid
			else:
				ng = mid
		res += 1
		start += ok + 1
	print(res)


from collections import defaultdict
for _ in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split()]
	m = int(input())
	e = [0] * (n + 1)
	for i in range(m):
		(x, y) = map(int, input().split())
		e[y] = max(e[y], x)
	maxr = e[-1]
	for i in range(n, 0, -1):
		maxr = max(maxr, e[i])
		e[i] = maxr
	ind = 1
	days = 0
	i = 0
	maxi = a[0]
	while i < n:
		maxi = max(maxi, a[i])
		if maxi <= e[ind]:
			ind += 1
			if i == n - 1:
				days += 1
		elif ind == 1:
			days = -1
			break
		else:
			ind = 1
			maxi = a[i]
			i -= 1
			days += 1
		i += 1
	print(days)


import sys
input = sys.stdin.readline
T = int(input())
Ans = []
for _ in range(T):
	N = int(input())
	A = list(map(int, input().split()))
	M = int(input())
	PS = [list(map(int, input().split())) for _ in range(M)]
	L = [0] * (N + 1)
	for (p, s) in PS:
		L[s] = max(L[s], p)
	for i in range(N - 1, -1, -1):
		L[i] = max(L[i], L[i + 1])
	ans = 1
	cnt = 1
	ma = 0
	if L[1] < max(A):
		Ans.append(-1)
		continue
	for a in A:
		ma = max(ma, a)
		if L[cnt] < ma:
			cnt = 1
			ans += 1
			ma = a
		cnt += 1
	Ans.append(ans)
print('\n'.join(map(str, Ans)))


from __future__ import print_function
from collections import Counter, OrderedDict
from itertools import permutations as perm
from collections import deque
from sys import stdin
from bisect import *
from heapq import *
import math
g = lambda : stdin.readline().strip()
gl = lambda : g().split()
gil = lambda : [int(var) for var in gl()]
gfl = lambda : [float(var) for var in gl()]
gcl = lambda : list(g())
gbs = lambda : [int(var) for var in g()]
mod = int(1000000000.0) + 7
inf = float('inf')
(t,) = gil()

def getLimit(x):
	idx = n - 1
	(l, r) = (0, m - 1)
	while l <= r:
		mid = (l + r) // 2
		if ps[mid][0] >= x:
			idx = mid
			r = mid - 1
		else:
			l = mid + 1
	return ps[idx][1]
for _ in range(t):
	(n,) = gil()
	a = gil()
	(m,) = gil()
	ps = []
	for _ in range(m):
		ps.append(gil())
	if max(ps, key=lambda x: x[0])[0] < max(a):
		print(-1)
	else:
		ps.sort()
		for i in reversed(range(m - 1)):
			ps[i][1] = max(ps[i + 1][1], ps[i][1])
		prev = a[0]
		cnt = 1
		lmt = getLimit(a[0])
		ans = 1
		for i in range(1, n):
			if a[i] > prev:
				prev = a[i]
				lmt = getLimit(a[i])
				if cnt + 1 > lmt:
					ans += 1
					cnt = 1
				else:
					cnt += 1
			elif cnt + 1 <= lmt:
				cnt += 1
			else:
				lmt = getLimit(a[i])
				prev = a[i]
				cnt = 1
				ans += 1
		print(ans)


from sys import stdin
input = stdin.readline
q = int(input())
for rew in range(q):
	n = int(input())
	monster = list(map(int, input().split()))
	m = int(input())
	rycerz = [list(map(int, input().split())) for i in range(m)]
	rycerz.sort()
	rycerz.reverse()
	p = [a[0] for a in rycerz]
	s = [a[1] for a in rycerz]
	maxendu = [-1] * m
	maxendu[0] = s[0]
	if max(p) < max(monster):
		print(-1)
	else:
		for i in range(1, m):
			maxendu[i] = max(maxendu[i - 1], s[i])
		days = 0
		poz = 0
		while True:
			if poz >= n:
				print(days)
				break
			best_potwor = -1
			kroki = 0
			while True:
				if poz + kroki >= n:
					break
				best_potwor = max(monster[poz + kroki], best_potwor)
				l = 0
				pr = m - 1
				while abs(pr - l) > 0:
					sr = (l + pr + 1) // 2
					if p[sr] >= best_potwor:
						l = sr
					else:
						pr = sr - 1
				sr = (pr + l) // 2
				if maxendu[sr] >= kroki + 1:
					kroki += 1
				else:
					kroki -= 1
					break
			days += 1
			poz += kroki
			poz += 1


import math
import sys
import os
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def listt():
	return [int(i) for i in input().split()]

def gcd(a, b):
	return math.gcd(a, b)

def lcm(a, b):
	return a * b // gcd(a, b)

def factors(n):
	step = 2 if n % 2 else 1
	return set(reduce(list.__add__, ([i, n // i] for i in range(1, int(math.sqrt(n)) + 1, step) if n % i == 0)))

def comb(n, k):
	factn = math.factorial(n)
	factk = math.factorial(k)
	fact = math.factorial(n - k)
	ans = factn // (factk * fact)
	return ans

def is_prime(n):
	if n <= 1:
		return False
	if n == 2:
		return True
	if n > 2 and n % 2 == 0:
		return False
	max_div = math.floor(math.sqrt(n))
	for i in range(3, 1 + max_div, 2):
		if n % i == 0:
			return False
	return True

def maxpower(n, x):
	B_max = int(math.log(n, x)) + 1
	return B_max

def binaryToDecimal(n):
	return int(n, 2)
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	m = int(input())
	d = [0] * (n + 1)
	for i in range(m):
		(u, v) = map(int, input().split())
		d[v] = max(d[v], u)
	for i in range(n - 1, -1, -1):
		d[i] = max(d[i], d[i + 1])
	ans = 1
	cnt = 1
	ma = 0
	if d[1] < max(arr):
		ans = -1
	else:
		for i in arr:
			ma = max(ma, i)
			if d[cnt] < ma:
				cnt = 1
				ans += 1
				ma = i
			cnt += 1
	print(ans)


import sys
input = sys.stdin.readline
from bisect import *
a = int(input())
for i in range(a):
	x = int(input())
	z = list(map(int, input().split()))
	r = int(input())
	ans = []
	for i in range(r):
		(x, y) = map(int, input().split())
		ans.append([x, y])
	ans.sort()
	power = [0 for i in range(len(ans))]
	maxa = [0 for i in range(len(ans))]
	for i in range(len(ans) - 1, -1, -1):
		if i == len(ans) - 1:
			maxa[i] = ans[i][1]
			power[i] = ans[i][0]
		elif ans[i][1] > maxa[i + 1]:
			power[i] = ans[i][0]
			maxa[i] = ans[i][1]
		else:
			maxa[i] = maxa[i + 1]
	t1 = []
	t2 = []
	for i in range(len(power)):
		if power[i]:
			t1.append(power[i])
			t2.append(maxa[i])
	maxa = []
	power = []
	for i in range(len(t2) - 1, -1, -1):
		if i == len(t2) - 1:
			maxa.append(t2[i])
			power.append(t1[i])
		else:
			maxa.append(t2[i])
			power.append(t1[i])
	days = 0
	i = 0
	flag = 0
	while i < len(z):
		cure = 0
		stam = 0
		if z[i] > power[0]:
			flag = 1
			break
		else:
			while i < len(z):
				cure = max(cure, z[i])
				stam += 1
				m = bisect_left(maxa, stam)
				if m == len(maxa) or power[m] < cure:
					days += 1
					break
				else:
					i += 1
			if i == len(z):
				days += 1
	if flag == 1:
		print(-1)
	else:
		print(days)


from sys import stdin
input = stdin.readline
import bisect
for xoxo in range(1):
	for _ in range(int(input())):
		n = int(input())
		a = list(map(int, input().split()))
		b = []
		sn = int(input())
		for i in range(sn):
			(p, s) = map(int, input().split())
			b.append([p, s])
		b.sort()
		p = [b[-1][0]]
		s = [b[-1][1]]
		k = sn - 1
		for i in range(sn - 2, -1, -1):
			if b[k][1] >= b[i][1]:
				continue
			k = i
			p.append(b[i][0])
			s.append(b[i][1])
		p.reverse()
		s.reverse()
		k = 0
		if max(a) > p[-1]:
			print('-1')
			continue
		ans = 0
		m = 0
		while k < n:
			q = 0
			t = 0
			while k + t < n:
				q = max(a[k + t], q)
				j = bisect.bisect_left(p, q)
				if s[j] <= t:
					break
				else:
					t += 1
			k += t
			ans += 1
		print(ans)


tests = int(input())
for i in range(tests):
	rez = 0
	k = 0
	n = int(input())
	powers = list(map(int, input().split()))
	m = int(input())
	vect = []
	powers = [0] + powers
	vect = [0] * (n + 1)
	for j in range(0, m):
		prop = list(map(int, input().split()))
		p = prop[0]
		s = prop[1]
		vect[s] = max(vect[s], p)
	for j in range(n - 1, -1, -1):
		vect[j] = max(vect[j], vect[j + 1])
	while k < n:
		a = 0
		b = 0
		while k + b <= n - 1 and vect[b + 1] >= max(a, powers[k + b + 1]):
			a = max(a, powers[k + b + 1])
			b = b + 1
		if b == 0:
			rez = -1
			break
		k = k + b
		rez = rez + 1
	print(rez)


import sys
import string
import math
import bisect as bi
from collections import defaultdict as dd
input = sys.stdin.readline

def cin():
	return map(int, sin().split())

def ain():
	return list(map(int, sin().split()))

def sin():
	return input()

def inin():
	return int(input())

def pref(a, n):
	pre = [0] * n
	pre[0] = a[0]
	for i in range(1, n):
		pre[i] = a[i] + pre[i - 1]
	return pre
for i in range(inin()):
	n = inin()
	mons = ain()
	h = inin()
	maxpowH = [0] * (n + 1)
	for i in range(h):
		(a, b) = cin()
		maxpowH[b] = max(maxpowH[b], a)
	for i in range(n - 1, -1, -1):
		maxpowH[i] = max(maxpowH[i + 1], maxpowH[i])
	if max(maxpowH) < max(mons):
		print(-1)
	else:
		ans = 0
		j = 0
		i = 0
		maxpowM = 0
		while i < n:
			maxpowM = max(maxpowM, mons[i])
			if maxpowM <= maxpowH[j + 1]:
				i += 1
				j += 1
			else:
				ans += 1
				j = 0
				maxpowM = 0
		if j > 0:
			ans += 1
		print(ans)


import sys
for t in range(int(sys.stdin.readline())):
	mm = int(sys.stdin.readline())
	m = [int(i) for i in sys.stdin.readline().split()]
	hh = int(sys.stdin.readline())
	h = []
	for j in range(hh):
		h.append([int(i) for i in sys.stdin.readline().split()])
	dp = [-1] * (mm + 1)
	for hhh in h:
		dp[hhh[1]] = max(hhh[0], dp[hhh[1]])
	for j in range(mm - 1, -1, -1):
		dp[j] = max(dp[j], dp[j + 1])
	ind = 0
	ans = 0
	while ind < mm:
		cnt = 0
		mx_p = 0
		while ind + cnt < mm:
			mx_p = max(mx_p, m[ind + cnt])
			if dp[cnt + 1] >= mx_p:
				cnt += 1
			else:
				break
		if cnt == 0:
			ans = -1
			break
		else:
			ind += cnt
			ans += 1
	print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	m = int(input())
	heroes = []
	bst = [0 for i in range(n + 1)]
	for _ in range(m):
		(x, y) = map(int, input().split())
		bst[y] = max(bst[y], x)
	for i in range(n - 1, -1, -1):
		bst[i] = max(bst[i], bst[i + 1])
	pos = 0
	res = 0
	yes = True
	while pos < n:
		res += 1
		npos = pos
		mx = 0
		while npos < n:
			mx = max(mx, a[npos])
			if mx > bst[npos - pos + 1]:
				break
			npos += 1
		if pos == npos:
			yes = False
			break
		pos = npos
	if not yes:
		res = -1
	print(res)


import sys
from collections import defaultdict
t = int(input())
for kkk in range(t):
	n = int(input())
	a = list(map(int, sys.stdin.readline().split()))
	pst = [0] * len(a)
	m = int(sys.stdin.readline())
	for i in range(m):
		(p, s) = map(int, sys.stdin.readline().split())
		s = min(s - 1, len(a) - 1)
		pst[s] = max(p, pst[s])
	for i in range(len(pst) - 2, -1, -1):
		pst[i] = max(pst[i], pst[i + 1])
	s = 1
	i = 0
	j = 0
	f = False
	maX = 0
	while i < len(a):
		maX = max(a[i], maX)
		if pst[j] >= maX:
			i += 1
			j += 1
		else:
			if j == 0:
				print(-1)
				f = True
				break
			j = 0
			s += 1
			maX = 0
	if not f:
		print(s)


import sys
import collections
from collections import Counter
import itertools
import math
import timeit
input = sys.stdin.readline

def sieve(n):
	if n < 2:
		return list()
	prime = [True for _ in range(n + 1)]
	p = 3
	while p * p <= n:
		if prime[p]:
			for i in range(p * 2, n + 1, p):
				prime[i] = False
		p += 2
	r = [2]
	for p in range(3, n + 1, 2):
		if prime[p]:
			r.append(p)
	return r

def divs(n, start=1):
	divisors = []
	for i in range(start, int(math.sqrt(n) + 1)):
		if n % i == 0:
			if n / i == i:
				divisors.append(i)
			else:
				divisors.extend([i, n // i])
	return divisors

def divn(n, primes):
	divs_number = 1
	for i in primes:
		if n == 1:
			return divs_number
		t = 1
		while n % i == 0:
			t += 1
			n //= i
		divs_number *= t

def flin(d, x, default=-1):
	left = right = -1
	for i in range(len(d)):
		if d[i] == x:
			if left == -1:
				left = i
			right = i
	if left == -1:
		return (default, default)
	else:
		return (left, right)

def ceil(n, k):
	return n // k + (n % k != 0)

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

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

def li():
	return list(map(int, input().split()))

def lcm(a, b):
	return abs(a * b) // math.gcd(a, b)

def prr(a, sep=' '):
	print(sep.join(map(str, a)))

def dd():
	return collections.defaultdict(int)
t = ii()
for _ in range(t):
	n = ii()
	d = li()
	m = ii()
	p = []
	for i in range(m):
		(a, b) = mi()
		p.append([a, b])
	p.sort(reverse=True)
	ps = [p[0]]
	for i in range(1, m):
		if p[i][1] > ps[-1][1]:
			ps.append(p[i])
	ps.reverse()
	if max(d) > ps[-1][0]:
		print(-1)
		continue
	res = 0
	i = 0
	while i < n:
		cmax = 0
		c = 1
		i + 1
		while i < n:
			cmax = max(cmax, d[i])
			ans = -1
			(l, r) = (0, len(ps) - 1)
			while l <= r:
				mid = l + (r - l) // 2
				if ps[mid][0] >= cmax and ps[mid][1] >= c:
					ans = mid
					break
				elif ps[mid][1] >= c:
					l = mid + 1
				elif ps[mid][0] >= cmax:
					r = mid - 1
				else:
					break
			if ans == -1:
				break
			c += 1
			i += 1
		res += 1
	print(res)


import sys
from functools import lru_cache, cmp_to_key
from heapq import merge, heapify, heappop, heappush
from math import *
from collections import defaultdict as dd, deque, Counter as C
from itertools import combinations as comb, permutations as perm
from bisect import bisect_left as bl, bisect_right as br, bisect
from time import perf_counter
from fractions import Fraction
mod = int(pow(10, 9) + 7)
mod2 = 998244353

def data():
	return sys.stdin.readline().strip()

def out(*var, end='\n'):
	sys.stdout.write(' '.join(map(str, var)) + end)

def l():
	return list(sp())

def sl():
	return list(ssp())

def sp():
	return map(int, data().split())

def ssp():
	return map(str, data().split())

def l1d(n, val=0):
	return [val for i in range(n)]

def l2d(n, m, val=0):
	return [l1d(n, val) for j in range(m)]
for _ in range(l()[0]):
	n = int(input())
	a = [0] + list(map(int, input().split()))
	m = int(input())
	l = [0] * (n + 1)
	for i in range(0, m):
		(p, s) = map(int, input().split())
		l[s] = max(l[s], p)
	for i in range(n - 1, -1, -1):
		l[i] = max(l[i], l[i + 1])
	ans = 0
	k = 0
	while k < n:
		q = 0
		t = 0
		while k + t + 1 <= n and l[t + 1] >= max(q, a[k + t + 1]):
			q = max(q, a[k + t + 1])
			t += 1
		if t == 0:
			ans = -1
			break
		k += t
		ans += 1
	print(ans)


def main():
	import sys
	from operator import itemgetter
	import bisect
	input = sys.stdin.readline
	t = int(input())
	for _ in range(t):
		N = int(input())
		A = list(map(int, input().split()))
		M = int(input())
		info = []
		for _ in range(M):
			(p, s) = map(int, input().split())
			info.append((p, s))
		info.sort(key=itemgetter(0), reverse=True)
		info.sort(key=itemgetter(1), reverse=True)
		P = []
		S = []
		pmax = 0
		for (p, s) in info:
			if p > pmax:
				P.append(p)
				S.append(s)
				pmax = p
		lenP = len(P)
		d = 0
		ans = 0
		while True:
			i = bisect.bisect_left(P, A[d])
			if i == lenP:
				ans = -1
				break
			ans += 1
			cnt = 0
			while cnt < S[i]:
				if P[i] >= A[d]:
					d += 1
					cnt += 1
					if d == N:
						break
				else:
					i += 1
					if i == lenP:
						break
			if d == N:
				break
		print(ans)
main()


import sys
readline = sys.stdin.readline
readlines = sys.stdin.readlines
ns = lambda : readline().rstrip()
ni = lambda : int(readline().rstrip())
nm = lambda : map(int, readline().split())
nl = lambda : list(map(int, readline().split()))
prn = lambda x: print(*x, sep='\n')

def solve():
	n = ni()
	a = nl()
	m = ni()
	g = [0] * (n + 2)
	for _ in range(m):
		(s, p) = nm()
		g[p] = max(g[p], s)
	for i in range(n, -1, -1):
		g[i] = max(g[i], g[i + 1])
	if max(a) > max(g):
		print(-1)
		return
	ans = idx = 0
	while idx < n:
		cm = a[idx]
		ct = 1
		while idx + ct < n and max(cm, a[idx + ct]) <= g[ct + 1]:
			cm = max(cm, a[idx + ct])
			ct += 1
		ans += 1
		idx += ct
	print(ans)
	return
T = ni()
for _ in range(T):
	solve()


class SegmentTree:

	def __init__(self, arr, func, initialRes=0):
		self.f = func
		self.N = len(arr)
		self.tree = [0 for _ in range(4 * self.N)]
		self.initialRes = initialRes
		for i in range(self.N):
			self.tree[self.N + i] = arr[i]
		for i in range(self.N - 1, 0, -1):
			self.tree[i] = self.f(self.tree[i << 1], self.tree[i << 1 | 1])

	def updateTreeNode(self, idx, value):
		self.tree[idx + self.N] = value
		idx += self.N
		i = idx
		while i > 1:
			self.tree[i >> 1] = self.f(self.tree[i], self.tree[i ^ 1])
			i >>= 1

	def query(self, l, r):
		r += 1
		res = self.initialRes
		l += self.N
		r += self.N
		while l < r:
			if l & 1:
				res = self.f(res, self.tree[l])
				l += 1
			if r & 1:
				r -= 1
				res = self.f(res, self.tree[r])
			l >>= 1
			r >>= 1
		return res

def getMaxSegTree(arr):
	return SegmentTree(arr, lambda a, b: max(a, b), initialRes=-float('inf'))

def getMinSegTree(arr):
	return SegmentTree(arr, lambda a, b: min(a, b), initialRes=float('inf'))

def getSumSegTree(arr):
	return SegmentTree(arr, lambda a, b: a + b, initialRes=0)

def main():

	def checkPossible(currMonster, furthestMonster):
		maxMonsterPower = maxAST.query(currMonster, furthestMonster)
		requiredendurance = furthestMonster - currMonster + 1
		i = -1
		b = m
		while b > 0:
			while i + b < m and ps[i + b][0] < maxMonsterPower:
				i += b
			b //= 2
		i += 1
		maxHeroEndurance = suffixMaxEndurance[i]
		return maxHeroEndurance >= requiredendurance
	t = int(input())
	allans = []
	for _ in range(t):
		n = int(input())
		a = readIntArr()
		m = int(input())
		ps = []
		for __ in range(m):
			ps.append(readIntArr())
		ps.sort(key=lambda x: x[0])
		if ps[-1][0] < max(a):
			allans.append(-1)
			continue
		maxAST = getMaxSegTree(a)
		suffixMaxEndurance = [-inf for _ in range(m)]
		for i in range(m - 1, -1, -1):
			suffixMaxEndurance[i] = ps[i][1]
			if i + 1 < m:
				suffixMaxEndurance[i] = max(suffixMaxEndurance[i], suffixMaxEndurance[i + 1])
		nDays = 0
		currMonster = 0
		while currMonster < n:
			nDays += 1
			furthestMonster = currMonster
			b = n
			while b > 0:
				while furthestMonster + b < n and checkPossible(currMonster, furthestMonster + b):
					furthestMonster += b
				b //= 2
			currMonster = furthestMonster + 1
		allans.append(nDays)
	multiLineArrayPrint(allans)
	return
import sys
input = sys.stdin.buffer.readline

def oneLineArrayPrint(arr):
	print(' '.join([str(x) for x in arr]))

def multiLineArrayPrint(arr):
	print('\n'.join([str(x) for x in arr]))

def multiLineArrayOfArraysPrint(arr):
	print('\n'.join([' '.join([str(x) for x in y]) for y in arr]))

def readIntArr():
	return [int(x) for x in input().split()]

def makeArr(defaultVal, dimensionArr):
	dv = defaultVal
	da = dimensionArr
	if len(da) == 1:
		return [dv for _ in range(da[0])]
	else:
		return [makeArr(dv, da[1:]) for _ in range(da[0])]

def queryInteractive(x, y):
	print('? {} {}'.format(x, y))
	sys.stdout.flush()
	return int(input())

def answerInteractive(ans):
	print('! {}'.format(ans))
	sys.stdout.flush()
inf = float('inf')
MOD = 10 ** 9 + 7
for _abc in range(1):
	main()


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from math import factorial
from collections import Counter, defaultdict
from heapq import heapify, heappop, heappush

def RL():
	return map(int, sys.stdin.readline().rstrip().split())

def RLL():
	return list(map(int, sys.stdin.readline().rstrip().split()))

def N():
	return int(input())

def comb(n, m):
	return factorial(n) / (factorial(m) * factorial(n - m)) if n >= m else 0

def perm(n, m):
	return factorial(n) // factorial(n - m) if n >= m else 0

def mdis(x1, y1, x2, y2):
	return abs(x1 - x2) + abs(y1 - y2)
mod = 1000000007
INF = float('inf')
from bisect import bisect_left

def main():
	for _ in range(N()):
		n = N()
		arrn = RLL()
		m = N()
		hero = []
		for _ in range(m):
			(p, s) = RL()
			hero.append((p, s))
		hero.sort()
		use = []
		for i in hero:
			while use and use[-1][1] < i[1]:
				use.pop()
			use.append(i)
		far = n + 1
		now = 0
		res = 1
		for i in arrn:
			p = bisect_left(use, (i, 0))
			if p >= len(use):
				print(-1)
				break
			if use[p][1] >= now + 1 and far >= now + 1:
				now += 1
				far = min(far, use[p][1])
			else:
				res += 1
				now = 1
				far = use[p][1]
		else:
			print(res)
main()


from collections import deque
import sys
import bisect

def inp():
	return sys.stdin.readline().strip()
for _ in range(int(inp())):
	n = int(inp())
	a = list(map(int, inp().split()))
	m = int(inp())
	hero = []
	for i in range(m):
		(x, y) = map(int, inp().split())
		hero.append((x, y))
	hero.sort()
	power = [0] * m
	freq = [0] * m
	freq[m - 1] = hero[m - 1][1]
	power[m - 1] = hero[m - 1][0]
	for i in range(m - 2, -1, -1):
		freq[i] = max(freq[i + 1], hero[i][1])
		power[i] = hero[i][0]
	d = 1
	f = True
	mxs = 0
	mxf = 0
	j = 0
	while j < n:
		mxs = max(mxs, a[j])
		mxf += 1
		k = bisect.bisect_left(power, mxs)
		if k == m and mxf == 1:
			f = False
			break
		elif k == m or freq[k] < mxf:
			d += 1
			mxs = 0
			mxf = 0
			continue
		j += 1
	if f:
		print(d)
	else:
		print(-1)


import sys
sin = sys.stdin
t = int(sin.readline())
for _ in range(t):
	n = int(sin.readline())
	monpows = [int(x) for x in sin.readline().split()]
	m = int(sin.readline())
	endtopow = dict()
	maxhero = 0
	for _ in range(m):
		h = [int(x) for x in sin.readline().split()]
		maxhero = max(maxhero, h[0])
		if h[1] in endtopow:
			endtopow[h[1]] = max(h[0], endtopow[h[1]])
		else:
			endtopow[h[1]] = h[0]
	endurances = [0 for x in range(n + 2)]
	for i in range(len(endurances) - 2, -1, -1):
		if i in endtopow:
			endurances[i] = max(endurances[i + 1], endtopow[i])
		else:
			endurances[i] = endurances[i + 1]
	days = 0
	msofar = 0
	maxpow = 0
	i = 0
	cant = False
	while i < n:
		maxpow = max(maxpow, monpows[i])
		if maxpow > maxhero:
			cant = True
			break
		if maxpow <= endurances[msofar + 1]:
			i += 1
			msofar += 1
		else:
			msofar = 0
			maxpow = 0
			days += 1
	days += 1
	if not cant:
		print(days)
	else:
		print(-1)


import bisect
import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()
if sys.version_info[0] < 3:
	(sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
for _ in range(int(input())):
	n = int(input())
	ai = list(map(int, input().split()))
	m = int(input())
	heroes = []
	for i in range(m):
		(pi, si) = map(int, input().split())
		heroes.append((pi, si))
	heroes.sort()
	for i in range(len(heroes) - 2, -1, -1):
		if heroes[i][1] <= heroes[i + 1][1]:
			heroes[i] = heroes[i + 1]
	heroes = list(set(heroes))
	heroes.sort()
	m = len(heroes)
	power = []
	stamina = []
	for i in heroes:
		power.append(i[0])
		stamina.append(i[1])
	tag = False
	indexofmons = 0
	ans = 0
	while indexofmons < n:
		if tag == True or indexofmons == n:
			break
		index = indexofmons
		pomns = ai[indexofmons]
		staminareq = 1
		while index < n:
			pomns = max(pomns, ai[index])
			q = bisect.bisect_left(power, pomns)
			if q == m:
				tag = True
				ans = -2
				break
			elif stamina[q] < staminareq:
				indexofmons = index
				break
			staminareq += 1
			index += 1
		indexofmons = index
		ans += 1
	print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	m = int(input())
	h = [tuple(map(int, input().split())) for i in range(m)]
	h.sort(reverse=True)
	new_h = []
	prev = 0
	for (p, s) in h:
		if s > prev:
			new_h.append((p, s))
			prev = s
	h = new_h
	hum = 0
	res = 1
	cur = 0
	maxp = 0
	for mon in a:
		maxp = max(mon, maxp)
		cur += 1
		if mon > h[0][0]:
			res = -1
			break
		if hum < len(h) and cur > h[hum][1]:
			hum += 1
		if hum == len(h) or maxp > h[hum][0]:
			res += 1
			hum = 0
			cur = 1
			maxp = mon
	print(res)


from __future__ import division, print_function
from fractions import Fraction
import sys
import os
from io import BytesIO, IOBase
from itertools import *
import bisect
from heapq import *
from math import *
from copy import *
from collections import deque
from collections import Counter as counter
from itertools import combinations as comb
from itertools import permutations as permutate
from bisect import bisect_left as bl
from bisect import bisect_right as br
from bisect import bisect
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()
if sys.version_info[0] < 3:
	(sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
from types import GeneratorType

def iterative(f, stack=[]):

	def wrapped_func(*args, **kwargs):
		if stack:
			return f(*args, **kwargs)
		to = f(*args, **kwargs)
		while True:
			if type(to) is GeneratorType:
				stack.append(to)
				to = next(to)
				continue
			stack.pop()
			if not stack:
				break
			to = stack[-1].send(to)
		return to
	return wrapped_func
mod = 1000000007

def inp():
	return sys.stdin.readline().rstrip('\r\n')

def out(var):
	sys.stdout.write(str(var))

def lis():
	return list(map(int, inp().split()))

def stringlis():
	return list(map(str, inp().split()))

def sep():
	return map(int, inp().split())

def strsep():
	return map(str, inp().split())

def zerolist(n):
	return [0] * n

def nextline():
	out('\n')

def testcase(t):
	for p in range(t):
		solve()

def printlist(a):
	for p in range(0, len(a)):
		out(str(a[p]) + ' ')

def lcm(a, b):
	return a * b // gcd(a, b)

def power(a, b):
	ans = 1
	while b > 0:
		if b % 2 == 1:
			ans *= a
		a *= a
		b //= 2
	return ans

def ncr(n, r):
	return factorial(n) // (factorial(r) * factorial(max(n - r, 1)))

def isPrime(n):
	if n <= 1:
		return False
	if n <= 3:
		return True
	if n % 2 == 0 or n % 3 == 0:
		return False
	i = 5
	while i * i <= n:
		if n % i == 0 or n % (i + 2) == 0:
			return False
		i = i + 6
	return True

def chck(mx, endurance, heroes, help):
	ind = bl(heroes, [mx])
	if ind == len(heroes):
		return False
	if help[ind] < endurance:
		return False
	return True

def solve():
	n = int(inp())
	a = lis()
	m = int(inp())
	heros = []
	maxpow = 0
	for i in range(m):
		(p, s) = sep()
		maxpow = max(maxpow, p)
		heros.append([p, s])
	heros = sorted(heros)
	help = [0] * (m + 1)
	for i in range(m - 1, -1, -1):
		help[i] = max(heros[i][1], help[i + 1])
	if maxpow < max(a):
		print(-1)
		return
	ans = 0
	prev = 0
	mx = 0
	for i in range(n):
		mx = max(mx, a[i])
		if chck(mx, i - prev + 1, heros, help):
			if i == n - 1:
				ans += 1
			continue
		else:
			ans += 1
			if i == n - 1:
				ans += 1
			prev = i
			mx = a[i]
	print(ans)
testcase(int(inp()))


t = int(input())
for i in range(t):
	n = int(input())
	monsters = list(map(int, input().split()))
	m = int(input())
	dct = {}
	lst = []
	now = 0
	index = 0
	for j in range(m):
		(a, b) = list(map(int, input().split()))
		if b > now or (b == now and dct[index][0] < a):
			index = j
			now = b
		dct[j] = [a, b]
		lst.append([a, j])
	lst.sort()
	sfx = []
	sfx.append([dct[lst[m - 1][1]][1], lst[m - 1][1]])
	for j in range(m - 2, -1, -1):
		(result1, i1) = sfx[-1]
		i2 = lst[j][1]
		result2 = dct[i2][1]
		if result2 > result1:
			sfx.append([result2, i2])
		else:
			sfx.append(sfx[-1])
	days = 1
	count = 0
	endurance = now
	strength = dct[index][0]
	for j in range(n):
		if endurance == 0:
			endurance = now
			strength = dct[index][0]
			days += 1
			count = 0
		if lst[-1][0] < monsters[j]:
			days = -1
			break
		if monsters[j] > strength:
			left = -1
			right = m - 1
			while left + 1 < right:
				mid = (left + right) // 2
				if lst[mid][0] >= monsters[j]:
					right = mid
				else:
					left = mid
			nxt = sfx[m - right - 1][1]
			strength = dct[nxt][0]
			endurance = dct[nxt][1] - count
			if endurance <= 0:
				endurance = dct[nxt][1]
				days += 1
				count = 0
		count += 1
		endurance -= 1
	print(days)


class UnionFindVerSize:

	def __init__(self, N):
		self._parent = [n for n in range(0, N)]
		self._size = [1] * N
		self.group = N

	def find_root(self, x):
		if self._parent[x] == x:
			return x
		self._parent[x] = self.find_root(self._parent[x])
		stack = [x]
		while self._parent[stack[-1]] != stack[-1]:
			stack.append(self._parent[stack[-1]])
		for v in stack:
			self._parent[v] = stack[-1]
		return self._parent[x]

	def unite(self, x, y):
		gx = self.find_root(x)
		gy = self.find_root(y)
		if gx == gy:
			return
		self.group -= 1
		if self._size[gx] < self._size[gy]:
			self._parent[gx] = gy
			self._size[gy] += self._size[gx]
		else:
			self._parent[gy] = gx
			self._size[gx] += self._size[gy]

	def get_size(self, x):
		return self._size[self.find_root(x)]

	def is_same_group(self, x, y):
		return self.find_root(x) == self.find_root(y)
import sys, random, bisect
from collections import deque, defaultdict
from heapq import heapify, heappop, heappush
from itertools import permutations
from math import log, gcd
input = lambda : sys.stdin.buffer.readline()
mi = lambda : map(int, input().split())
li = lambda : list(mi())
ans = []
for _ in range(int(input())):
	n = int(input())
	a = li()
	m = int(input())
	hero = [tuple(mi()) for i in range(m)]
	maxi = [0 for i in range(n + 1)]
	for (p, s) in hero:
		maxi[s] = max(maxi[s], p)
	for i in range(n - 1, 0, -1):
		maxi[i] = max(maxi[i], maxi[i + 1])
	res = 0
	next = 0
	while next < n:
		flag = False
		t = a[next]
		for i in range(1, n + 1):
			if maxi[i] >= t:
				flag = True
				next += 1
				if next == n:
					break
				else:
					t = max(t, a[next])
			else:
				break
		if not flag:
			ans.append(-1)
			break
		else:
			res += 1
	else:
		ans.append(res)
print(*ans, sep='\n')


from sys import stdin

def input():
	return next(stdin)

def main():

	def solve():
		n = int(input())
		aa = [int(a) for a in input().split()]
		m = int(input())
		pso = []
		for _ in range(m):
			(p, s) = map(int, input().split())
			pso.append((p, s))
		pso.sort(reverse=True)
		smax = 0
		ps = []
		for (p, s) in pso:
			if s > smax:
				smax = s
				if ps != [] and p == ps[-1][0]:
					ps[-1] = (p, s)
				else:
					ps.append((p, s))
		pos = 0
		count = 0
		while pos < n:
			d = 0
			ma = 0
			for (p, s) in ps:
				if d + pos >= n or p < ma or p < aa[d + pos]:
					break
				while s > d and d + pos < n and (p >= aa[d + pos]):
					if aa[d + pos] > ma:
						ma = aa[d + pos]
					d += 1
			if d == 0:
				print(-1)
				return
			count += 1
			pos += d
		print(count)
	q = int(input())
	for _ in range(q):
		solve()
main()