Chef has a sequence $A_{1}, A_{2}, \ldots, A_{N}$. For a positive integer $M$, sequence $B$ is defined as $B = A*M$ that is, appending $A$ exactly $M$ times. For example, If $A = [1, 2]$ and $M = 3$, then $B = A*M = [1, 2, 1, 2, 1, 2]$

You have to help him to find out the minimum value of $M$ such that the length of the longest strictly increasing subsequence is maximum possible.

------ Input: ------
The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
The first line of each test case contains a single integer $N$.
The second line contains $N$ space-separated integers $A_{1}, A_{2}, \ldots, A_{N}$.

------ Output: ------
For each test case, print a single line containing one integer ― the minimum value of $M$.

------ Constraints  ------
$1 ≤ T ≤ 500$
$1 ≤ N ≤ 2*10^{5}$
$1 ≤ A_{i} ≤ 10^{9}$
It's guaranteed that the total length of the sequence $A$ in one test file doesn't exceed $2*10^{6}$

----- Sample Input 1 ------ 
3
2
2 1
2
1 2
5
1 3 2 1 2
----- Sample Output 1 ------ 
2
1
2
----- explanation 1 ------ 
In the first test case, Choosing $M = 2$ gives $B = [2, 1, 2, 1]$ which has a longest strictly increasing sequence of length $2$ which is the maximum possible.

In the second test case, Choosing $M = 1$ gives $B  = [1, 2]$ which has a longest strictly increasing sequence of length $2$ which is the maximum possible.

Difficulty: MEDIUM_HARD
Tags: Implementation

Constructive algorithms

Starter code:

Solutions:
from collections import defaultdict
t = int(input())
for i in range(t):
	N = int(input())
	st = input().split()
	L = [[]]
	D = defaultdict(int)
	S = set()
	p = 0
	for x in st:
		n = int(x)
		if n in S:
			q = D[n]
		else:
			S.add(n)
			q = len(L)
			L.append([])
			D[n] = q
		L[q].append(p)
		p += 1
	SL = list(S)
	SL.sort()
	p = 0
	M = 1
	for n in SL:
		q = D[n]
		if len(L[q]) == 1:
			z = L[q][0]
			if z < p:
				M += 1
			p = z
		else:
			v = L[q][-1]
			if v > p:
				k = 0
				while L[q][k] < p:
					k += 1
				p = L[q][k]
			else:
				M += 1
				p = L[q][0]
	print(M)


from collections import defaultdict
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	ans = 1
	d = defaultdict(list)
	for i in range(n):
		d[arr[i]].append(i + 1)
	ind = -10 ** 10
	uno = list(set(arr))
	uno.sort()
	for i in uno:
		f = 0
		f2 = 0
		k = 0
		op = d[i]
		for j in op:
			if f2 == 0:
				f2 = 1
				ck = j
			if j > ind:
				ind = j
				f = 1
				break
		if f == 0:
			ind = ck
			ans += 1
	print(ans)


def bs(x, prev, pict):
	l = 0
	r = len(pict[x]) - 1
	while l <= r:
		if r - l < 5:
			for i in range(l, r + 1):
				if pict[x][i] > prev:
					return pict[x][i]
			return -1
		mid = (l + r) // 2
		if pict[x][mid] < prev:
			l = mid + 1
		else:
			r = mid
	return -1
t = int(input())
for _ in range(t):
	n = int(input())
	s = list(map(int, input().split()))
	li = []
	pict = {}
	for i in range(len(s)):
		if pict.get(s[i]) is None:
			pict[s[i]] = []
			li.append(s[i])
		pict[s[i]].append(i + 1)
	li.sort()
	count = 1
	prev = 0
	i = len(li)
	for i in range(len(li)):
		x = bs(li[i], prev, pict)
		if x != -1:
			prev = x
		else:
			count += 1
			prev = pict[li[i]][0]
	print(count)


from collections import defaultdict as dd
from bisect import insort as ins, bisect_right as br, bisect_left as bl
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().strip().split()))
	d = dd(list)
	for i in range(n):
		ins(d[l[i]], i)
	ct = 1
	j = 0
	for i in sorted(list(set(l))):
		ind = bl(d[i], j)
		if ind == len(d[i]):
			ct += 1
			j = d[i][0]
		else:
			j = d[i][ind]
	print(ct)


for t in range(int(input().strip())):
	n = int(input().strip())
	arr = tuple(map(int, input().strip().split()))
	d = dict()
	for i in range(n):
		a = arr[i]
		if a not in d:
			d[a] = []
		d[a].append(i)
	s = sorted(d.keys())
	pos = -1
	m = 1
	for a in s:
		p = d[a]
		mpos = p[0]
		isfound = False
		for i in p:
			if pos < i:
				isfound = True
				pos = i
				break
		if not isfound:
			pos = mpos
			m += 1
	print(m)


t = int(input())
while t:
	t -= 1
	n = int(input())
	a = [int(x) for x in input().split()]
	d = {}
	for i in range(n):
		try:
			d[a[i]].append(i)
		except:
			d[a[i]] = [i]
	p = -1
	ans = 1
	for i in sorted(d.keys()):
		f = 1
		for j in d[i]:
			if j > p:
				p = j
				f = 0
				break
		if f:
			p = d[i][0]
			ans = ans + 1
	print(ans)


from collections import defaultdict
t = int(input())
while t:
	n = int(input())
	a = list(map(int, input().split()))
	d = defaultdict(list)
	for i in range(n):
		d[a[i]].append(i)
	id = -1
	m = 1
	for i in sorted(d):
		f = 0
		for j in d[i]:
			if j > id:
				f = 1
				id = j
				break
		if f == 0:
			m += 1
			id = d[i][0]
	print(m)
	t -= 1


from collections import defaultdict
from bisect import bisect_right
for _ in range(int(input())):
	int(input())
	d = defaultdict(list)
	for (i, x) in enumerate(map(int, input().split())):
		d[x].append(i)
	(i, m) = (-1, 1)
	for x in sorted(d):
		l = d[x]
		j = bisect_right(l, i)
		i = l[j % len(l)]
		m += j // len(l)
	print(m)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	(b, m) = ([], 1)
	for i in range(len(a)):
		b.append([a[i], i])
	b.sort()
	i = 0
	while b[i][0] < b[n - 1][0]:
		j = i + 1
		while j < n and b[j][0] == b[i][0]:
			j += 1
		k = j + 1
		while k < n and b[k][0] == b[j][0]:
			k += 1
		y = j
		while y < k:
			if b[i][1] < b[y][1]:
				break
			y += 1
		if y == k:
			i = j
			m += 1
		else:
			i = y
	print(m)


for _ in range(int(input())):
	n = int(input())
	ar = list(map(int, input().split()))
	sett = list(set(ar))
	sett.sort()
	index = {i: [] for i in sett}
	for i in range(n):
		index[ar[i]].append(i)
	prv = None
	ans = 0
	for i in index:
		if prv == None:
			prv = min(index[i])
			ans += 1
			continue
		temp = max(index[i])
		if temp < prv:
			ans += 1
			prv = index[i][0]
			continue
		for j in index[i]:
			if prv < j:
				prv = j
				break
	print(ans)


from collections import *
t = int(input())
for i in range(t):
	n = int(input())
	a = [int(i) for i in input().split()]
	s = list(set(a))
	s.sort()
	d = defaultdict(list)
	for i in range(n):
		d[a[i]].append(i)
	ans = 1
	curpos = min(d[s[0]])
	for i in range(1, len(s)):
		if curpos > max(d[s[i]]):
			ans += 1
			curpos = min(d[s[i]])
		else:
			for j in d[s[i]]:
				if j > curpos:
					curpos = j
					break
	print(ans)


for _ in range(int(input())):
	n = int(input())
	list1 = list(map(int, input().split()))
	listset = list(set(list1))
	listset.sort()
	dict1 = {}
	for i in listset:
		dict1[i] = []
	for i in range(n):
		dict1[list1[i]].append(i)
	f = dict1[listset[0]][0]
	ans = 1
	for p in range(1, len(listset)):
		if dict1[listset[p]][-1] > f:
			for j in dict1[listset[p]]:
				if j > f:
					f = j
					break
		else:
			ans += 1
			f = dict1[listset[p]][0]
	print(ans)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	d = {}
	sr = list(set(a))
	sr.sort()
	for i in range(n):
		if a[i] in d:
			d[a[i]].append(i)
		else:
			d[a[i]] = [i]
	ans = 1
	st = d[sr[0]][0]
	for i in range(1, len(sr)):
		flag = 0
		for j in d[sr[i]]:
			if j > st:
				st = j
				flag = 1
				break
		if flag == 0:
			st = d[sr[i]][0]
			ans += 1
	print(ans)


def abc(l, m):
	i = 0
	j = len(l) - 1
	ans = -1
	while i <= j:
		mid = i + (j - i) // 2
		if l[mid] > m:
			ans = mid
			j = mid - 1
		else:
			i = mid + 1
	return ans
t = int(input())
for _ in range(t):
	n = int(input())
	ans = 0
	l = list(map(int, input().split()))
	d = {}
	for i in range(n):
		try:
			d[l[i]] += [i]
		except:
			d[l[i]] = [i]
	x = list(d.keys())
	x.sort()
	m = d[x[0]][0]
	for i in x[1:]:
		c = abc(d[i], m)
		if c == -1:
			ans += 1
			m = d[i][0]
		else:
			m = d[i][c]
	print(ans + 1)


from bisect import bisect_left
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	b = sorted(a)
	d = dict()
	for i in range(n):
		if not d.get(a[i], None):
			d[a[i]] = []
		d[a[i]].append(i)
	i = 0
	ans = 0
	pos = 0
	pre = -1
	while i < len(b):
		if pre == b[i]:
			i += 1
			continue
		pre = b[i]
		ind = bisect_left(d[b[i]], pos)
		if ind == len(d[b[i]]):
			ans += 1
			pos = d[b[i]][0]
		else:
			pos = d[b[i]][ind]
	print(ans + 1)


from collections import defaultdict
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	d = defaultdict(list)
	for i in range(n):
		d[a[i]].append(i)
	st = -100
	m = 1
	for i in sorted(d):
		for j in d[i]:
			if j > st:
				st = j
				break
		else:
			st = d[i][0]
			m += 1
	print(m)


def getNext(l, prev):
	if l[-1] < prev:
		return l[0]
	for x in l:
		if x > prev:
			return x
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	d = {}
	for i in range(n):
		if a[i] in d:
			d[a[i]].append(i)
		else:
			d[a[i]] = [i]
	keys = sorted(d)
	answer = 1
	prev = min(d[keys[0]])
	for i in range(1, len(keys)):
		nextid = getNext(d[keys[i]], prev)
		if nextid < prev:
			answer += 1
		prev = nextid
	print(answer)


from sys import stdin, stdout
import math
from itertools import permutations, combinations
from collections import defaultdict
from bisect import bisect_left

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

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

def I():
	return int(stdin.readline())
P = 1000000007
for t in range(I()):
	n = I()
	arr = L()
	dict1 = {}
	for i in range(n):
		if arr[i] in dict1.keys():
			dict1[arr[i]].append(i)
		else:
			dict1[arr[i]] = [i]
	keys = sorted(dict1.keys())
	l = len(keys)
	flag = 0
	ix = -1
	count = 0
	for i in range(l - 1):
		if not flag:
			ix = dict1[keys[i]][0]
			for j in dict1[keys[i + 1]]:
				if j > ix:
					ix = j
					flag = 1
					count += 1
					break
		else:
			flag = 0
			for j in dict1[keys[i + 1]]:
				if j > ix:
					ix = j
					flag = 1
					count += 1
					break
	print(l - count)


from collections import defaultdict
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	q = defaultdict(list)
	for i in range(n):
		q[a[i]].append(i)
	p = list(set(a))
	p.sort()
	ans = 1
	ind = -1
	for i in p:
		fg = 0
		x = q[i]
		for j in x:
			if j > ind:
				ind = j
				fg = 1
				break
		if fg == 0:
			ans += 1
			ind = q[i][0]
	print(ans)


t = int(input())
while t > 0:
	n = int(input())
	nums = list(map(int, input().split()))
	d = {}
	l = []
	for i in range(n):
		if nums[i] in d:
			d[nums[i]].append(i)
		else:
			d[nums[i]] = [i]
			l.append(nums[i])
	l.sort()
	k = n
	m = 0
	for i in range(len(l)):
		if d[l[i]][-1] < k:
			m += 1
			k = d[l[i]][0]
		else:
			p = d[l[i]]
			s = len(p)
			lo = 0
			hi = s - 1
			res = p[-1]
			while lo <= hi:
				mid = (lo + hi) // 2
				if p[mid] >= k:
					res = p[mid]
					hi = mid - 1
				else:
					lo = mid + 1
			k = res
	print(m)
	t -= 1


import bisect
mod = 1000000007
from math import gcd
import sys
input = sys.stdin.readline
from collections import defaultdict as dd, deque as dq
t = int(input())
while t:
	n = int(input())
	l = list(map(int, input().split()))
	d = dd(list)
	for i in range(n):
		d[l[i]].append(i)
	ls = sorted(list(set(l)))
	n = len(ls)
	pre = d[ls[0]][0]
	mx = -1
	le = 1
	ii = 1
	lol = 0
	cou = 1
	while ii < n:
		ind = bisect.bisect_left(d[ls[ii]], pre)
		if ind < len(d[ls[ii]]):
			le += 1
			pre = d[ls[ii]][ind]
			ii += 1
		else:
			cou += 1
			le = 1
			pre = d[ls[ii]][0]
			ii += 1
	print(cou)
	t -= 1


import collections
from sys import *
import bisect as bs
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	s = 1
	d = {}
	for i in range(n):
		if a[i] not in d:
			d[a[i]] = []
		d[a[i]].append(i)
	l = list(d.keys())
	l.sort()
	c = 0
	for j in l:
		ln = len(d[j])
		v = bs.bisect_left(d[j], c)
		if v == ln:
			c = d[j][0] + 1
			s += 1
			continue
		c = d[j][v] + 1
	print(s)


import math
import sys
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque
from functools import lru_cache, reduce
from heapq import heapify, heappop, heappush
from itertools import chain, combinations, permutations, product
from typing import List, Dict
sys.setrecursionlimit(10 ** 5 + 1)
input = sys.stdin.readline
write = sys.stdout.write

def read_int() -> int:
	return int(input())

def read_n_int() -> list:
	return [int(s) for s in input().split()]

def list2d(row, col, init=0) -> List[list]:
	return [[init] * col for _ in range(row)]
MOD = 10 ** 9 + 7
T = read_int()
for _ in range(T):
	N = read_int()
	nums = read_n_int()
	num_to_idx = defaultdict(list)
	for (i, num) in enumerate(nums):
		num_to_idx[num].append(i)
	pre_idx = N
	ans = 0
	for num in sorted(num_to_idx.keys()):
		cur_indices = num_to_idx[num]
		if cur_indices[-1] < pre_idx:
			pre_idx = num_to_idx[num][0]
			ans += 1
		else:
			pre_idx = cur_indices[bisect_right(cur_indices, pre_idx)]
	print(ans)


def findM(A, n):
	elemIdxMap = dict()
	for i in range(n):
		if A[i] in elemIdxMap:
			elemIdxMap[A[i]].append(i)
		else:
			elemIdxMap[A[i]] = [i]
	keys = sorted(elemIdxMap.keys())
	connected = False
	count = 0
	prevIdx = -1
	nKeys = len(keys)
	for i in range(nKeys - 1):
		if not connected:
			prevIdx = elemIdxMap[keys[i]][0]
			for idx in elemIdxMap[keys[i + 1]]:
				if idx > prevIdx:
					connected = True
					count += 1
					prevIdx = idx
					break
		else:
			connected = False
			for idx in elemIdxMap[keys[i + 1]]:
				if idx > prevIdx:
					connected = True
					count += 1
					prevIdx = idx
					break
	return nKeys - count
for _ in range(int(input())):
	n = int(input())
	A = list(map(int, input().split()))
	print(findM(A, n))


T = int(input())
for _ in range(T):
	n = int(input())
	l = list(map(int, input().split()))
	fin = list(set(l))
	fin.sort()
	ans = 1
	dic = dict()
	for i in range(len(l)):
		if l[i] not in dic.keys():
			dic[l[i]] = [i]
		else:
			dic[l[i]].append(i)
	prev = dic[fin[0]][0]
	for i in range(1, len(fin)):
		flag = 0
		for ind in dic[fin[i]]:
			if ind > prev:
				prev = ind
				flag = 1
				break
		if flag == 0:
			ans += 1
			prev = dic[fin[i]][0]
	print(ans)


import bisect
from collections import defaultdict
for _ in range(int(input())):
	n = int(input())
	count = 0
	a = list(map(int, input().split()))
	d = defaultdict(list)
	for i in range(n):
		d[a[i]].append(i)
	x = list(d.keys())
	x.sort()
	p = d[x[0]][0]
	for i in range(1, len(x)):
		l = bisect.bisect_right(d[x[i]], p)
		if l == len(d[x[i]]):
			p = d[x[i]][0]
			count += 1
		else:
			p = d[x[i]][l]
	print(count + 1)


def mForMaxSeq(arr, n):
	eim = dict()
	for i in range(n):
		if arr[i] in eim:
			eim[arr[i]].append(i)
		else:
			eim[arr[i]] = [i]
	keys = sorted(eim.keys())
	connected = False
	count = 0
	pI = -1
	nKeys = len(keys)
	for i in range(nKeys - 1):
		if not connected:
			pI = eim[keys[i]][0]
			for idx in eim[keys[i + 1]]:
				if idx > pI:
					connected = True
					count += 1
					pI = idx
					break
		else:
			connected = False
			for idx in eim[keys[i + 1]]:
				if idx > pI:
					connected = True
					count += 1
					pI = idx
					break
	return nKeys - count
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	print(mForMaxSeq(arr, n))


t = int(input())
for j in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	s = list(set(l))
	s.sort()
	dic = {}
	le = {}
	for j in s:
		dic[j] = []
		le[j] = 0
	for j in range(n):
		dic[l[j]].append(j + 1)
		le[l[j]] += 1
	stack = [dic[s[0]][0]]
	z = 0
	m = 1
	x = len(s)
	for j in range(1, x):
		flag = 0
		for k in range(le[s[j]]):
			if dic[s[j]][k] + (m - 1) * n > stack[z]:
				stack.append(dic[s[j]][k] + (m - 1) * n)
				z += 1
				flag = 1
				break
		if flag == 0:
			m += 1
			stack.append(dic[s[j]][0] + (m - 1) * n)
			z += 1
	print(m)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	u = list(set(l))
	u.sort()
	d = {}
	for i in u:
		d[i] = []
	for i in range(n):
		d[l[i]].append(i)
	f = d[u[0]][0]
	p = 1
	m = 1
	while p < len(u):
		if d[u[p]][-1] > f:
			for j in d[u[p]]:
				if j > f:
					f = j
					p += 1
					break
		else:
			m += 1
			f = d[u[p]][0]
			p += 1
	print(m)


from collections import defaultdict
for _ in range(int(input())):
	n = int(input())
	s = [int(i) for i in input().split()]
	w = defaultdict(list)
	for i in range(n):
		w[s[i]].append(i)
	typ = len(w)
	keys = sorted(list(w.keys()))
	length = len(keys)
	ele_count = 1
	i = 1
	rnd = 0
	val = keys[0]
	pos = w[keys[0]][0]
	while ele_count < typ:
		if w[keys[ele_count]][-1] < pos:
			rnd += 1
			pos = w[keys[ele_count]][0]
		else:
			i = 0
			while i < len(w[keys[ele_count]]) and w[keys[ele_count]][i] <= pos:
				i += 1
			pos = w[keys[ele_count]][i]
		ele_count += 1
	print(rnd + 1)


import collections
import bisect
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	d = collections.defaultdict(list)
	(c, find, ans, l) = (0, 0, 0, [])
	for i in range(n):
		if a[i] not in d:
			l.append(a[i])
			c += 1
		d[a[i]].append(i)
	l.sort()
	for i in range(c):
		if i == 0:
			ans += 1
			find = d[l[i]][0] + 1
		else:
			k = bisect.bisect_left(d[l[i]], find)
			if k == 0:
				find = d[l[i]][k] + 1
			elif k == len(d[l[i]]):
				find = d[l[i]][0] + 1
				ans += 1
			else:
				find = d[l[i]][k] + 1
	print(ans)


from sys import stdin
for _ in range(int(stdin.readline())):
	n = int(stdin.readline())
	arr = list(map(int, stdin.readline().split()))
	final = {}
	m = sorted(list(set(arr)))
	count = 0
	d = {}
	for i in range(n):
		if arr[i] in d:
			d[arr[i]].append(i)
		else:
			d[arr[i]] = [i]
	pos = d[m[0]][0]
	j = 1
	while j < len(m):
		k = None
		for item in d[m[j]]:
			if item > pos:
				k = item
				break
		if k != None:
			j += 1
			pos = k
		else:
			count += 1
			pos = -1
	print(count + 1)


from collections import defaultdict
from bisect import bisect_right
I = input
t = int(I())
for _ in range(t):
	I()
	d = defaultdict(list)
	for (i, x) in enumerate(map(int, I().split())):
		d[x].append(i)
	(i, m) = (-1, 1)
	for x in sorted(d):
		l = d[x]
		j = bisect_right(l, i)
		if j < len(l):
			i = l[j]
		else:
			m += 1
			i = l[0]
	print(m)


t = int(input())
while t:
	t -= 1
	n = int(input())
	a = list(map(int, input().split()))
	s = list(set(a))
	s.sort()
	ind = dict()
	for i in range(n):
		if a[i] in ind:
			ind[a[i]].append(i)
		else:
			ind[a[i]] = [i]
	s1 = 1
	ref = -1
	for i in s:
		flag = 0
		for j in ind[i]:
			if j > ref:
				ref = j
				flag = 1
				break
		if flag == 0:
			s1 += 1
			ref = ind[i][0]
	print(s1)


for T in range(int(input())):
	N = int(input())
	a = list(map(int, input().split()))
	d = {}
	elements = []
	for i in range(N):
		if a[i] not in d:
			d[a[i]] = [i]
			elements.append(a[i])
		else:
			d[a[i]].append(i)
	elements.sort()
	M = 1
	prev_index = d[elements[0]][0]
	for i in range(1, len(elements)):
		flag = True
		for j in range(len(d[elements[i]])):
			if prev_index < d[elements[i]][j]:
				flag = False
				prev_index = d[elements[i]][j]
				break
		if flag:
			M += 1
			prev_index = d[elements[i]][0]
	print(M)


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	b = set(a)
	b = list(b)
	b.sort()
	c = dict()
	for i in range(n):
		if a[i] in c:
			c[a[i]].append(i)
		else:
			c[a[i]] = [i]
	index = -1
	count = 0
	for i in range(len(b)):
		r = c[b[i]]
		flag = 0
		for j in range(len(r)):
			if r[j] > index:
				flag = 1
				index = r[j]
				break
		if flag != 1:
			index = r[0]
			count += 1
	print(count + 1)


from collections import defaultdict
for _ in range(int(input())):
	n = int(input())
	s = list(map(int, input().split()))
	r = defaultdict(list)
	for i in range(n):
		r[s[i]].append(i)
	t = sorted(r.keys())
	N = len(t)
	l = r[t[0]][0]
	ans = 1
	for i in range(1, N):
		flag = 0
		for j in r[t[i]]:
			if j >= l:
				l = j
				flag = 1
				break
		if flag == 0:
			ans += 1
			l = r[t[i]][0]
	print(ans)


def main():
	from bisect import bisect_left as bl, bisect_right as br, insort
	import sys
	import heapq
	from collections import defaultdict as dd, deque

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

	def mdata():
		return list(map(int, data().split()))
	out = sys.stdout.write
	INF = int(1000000000.0)
	mod = int(1000000000.0) + 7
	for t in range(int(data())):
		n = int(data())
		A = mdata()
		d = dd(list)
		for i in range(n):
			d[A[i]].append(i)
		l = sorted(d.keys())
		cnt = 1
		ind = d[l[0]][0]
		for i in range(1, len(l)):
			k = bl(d[l[i]], ind)
			if k == len(d[l[i]]):
				cnt += 1
				ind = d[l[i]][0]
			else:
				ind = d[l[i]][k]
		print(cnt)
main()


from sys import stdin
input = stdin.readline
from bisect import bisect_right
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	d = {i: [] for i in a}
	for (i, j) in enumerate(a):
		d[j].append(i)
	ans = 1
	l = tuple((r[1] for r in sorted(d.items())))
	p = 0
	for i in range(len(l) - 1):
		x = bisect_right(l[i + 1], l[i][p])
		if x == len(l[i + 1]):
			ans += 1
			p = 0
		else:
			p = x
	print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	a = [int(x) for x in input().strip().split()]
	a = [(a[i], i) for i in range(n)]
	a.sort()
	res = 1
	prev = 0
	prev_ind = -1
	i = 0
	while i < n:
		if a[i][1] > prev_ind:
			prev_ind = a[i][1]
			prev = a[i][0]
			while i < n and a[i][0] == prev:
				i += 1
		else:
			prev = a[i][0]
			flag = False
			mn = a[i][1]
			while i < n and a[i][0] == prev:
				if a[i][1] > prev_ind:
					prev_ind = a[i][1]
					flag = True
					break
				i += 1
			if flag:
				while i < n and a[i][0] == prev:
					i += 1
			else:
				res += 1
				prev_ind = mn
	print(res)


import bisect

def solve(arr, n, ans):
	indices = {}
	dist_vals = []
	for i in range(n):
		if arr[i] not in indices.keys():
			indices[arr[i]] = []
			dist_vals.append(arr[i])
		indices[arr[i]].append(i)
	dist_vals.sort()
	m = 1
	index = -1
	i = 0
	while i < len(dist_vals):
		x = dist_vals[i]
		index = bisect.bisect(indices[x], index)
		if index == len(indices[x]):
			m += 1
			index = -1
		else:
			index = indices[x][index]
			i += 1
	ans.append(m)

def main():
	t = int(input())
	ans = []
	for i in range(t):
		n = int(input())
		arr = list(map(int, input().split()))
		solve(arr, n, ans)
	for i in ans:
		print(i)
main()


import math
import collections
from sys import *
import bisect as bs
T = int(stdin.readline())
for _ in range(T):
	n = int(stdin.readline())
	a = list(map(int, stdin.readline().split()))
	ans = 1
	d = {}
	for i in range(n):
		if a[i] not in d:
			d[a[i]] = []
		d[a[i]].append(i)
	dk = list(d.keys())
	dk.sort()
	cur = 0
	for k in dk:
		l = len(d[k])
		v = bs.bisect_left(d[k], cur)
		if v == l:
			cur = d[k][0] + 1
			ans += 1
			continue
		cur = d[k][v] + 1
	print(ans)


from collections import defaultdict
import bisect
t = int(input())
for i in range(t):
	n = int(input())
	A = [int(j) for j in input().split()]
	d = defaultdict(list)
	for (j, i) in enumerate(A):
		d[i].append(j)
	keys = sorted(d.keys())
	pk = 0
	ans = 1
	prev = None
	for i in keys:
		pos = bisect.bisect_left(d[i], pk)
		if pos == len(d[i]):
			pos = 0
			ans += 1
		pos = d[i][pos]
		pk = pos
	print(ans)


import sys
from collections import defaultdict
from copy import copy
MOD = 998244353
R = lambda t=int: t(input())
RL = lambda t=int: [t(x) for x in input().split()]
RLL = lambda n, t=int: [RL(t) for _ in range(n)]

def solve():
	n = R()
	A = RL()
	r = 1
	x = sorted(set(A))
	P = {}
	i = 0
	for a in A:
		if a not in P:
			P[a] = []
		P[a] += [i]
		i += 1
	l = len(x)
	i = 0
	p = -1
	r = 1
	for a in x:
		moved = False
		for x in P[a]:
			if x > p:
				p = x
				moved = True
				break
		if not moved:
			p = P[a][0]
			r += 1
	print(r)
T = R()
for _ in range(T):
	solve()