You are given a permutation $p_1, p_2, \dots, p_n$. Then, an undirected graph is constructed in the following way: add an edge between vertices $i$, $j$ such that $i < j$ if and only if $p_i > p_j$. Your task is to count the number of connected components in this graph.

Two vertices $u$ and $v$ belong to the same connected component if and only if there is at least one path along edges connecting $u$ and $v$.

A permutation is an array consisting of $n$ distinct integers from $1$ to $n$ in arbitrary order. For example, $[2,3,1,5,4]$ is a permutation, but $[1,2,2]$ is not a permutation ($2$ appears twice in the array) and $[1,3,4]$ is also not a permutation ($n=3$ but there is $4$ in the array).


-----Input-----

Each test contains multiple test cases. The first line contains a single integer $t$ ($1 \le t \le 10^5$) — the number of test cases. Description of the test cases follows.

The first line of each test case contains a single integer $n$ ($1 \le n \le 10^5$) — the length of the permutation.

The second line of each test case contains $n$ integers $p_1, p_2, \dots, p_n$ ($1 \le p_i \le n$) — the elements of the permutation.

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


-----Output-----

For each test case, print one integer $k$ — the number of connected components.


-----Examples-----

Input
6
3
1 2 3
5
2 1 4 3 5
6
6 1 4 2 5 3
1
1
6
3 2 1 6 5 4
5
3 1 5 2 4
Output
3
3
1
1
2
1


-----Note-----

Each separate test case is depicted in the image below. The colored squares represent the elements of the permutation. For one permutation, each color represents some connected component. The number of distinct colors is the answer.

Source: codeforces | Difficulty: EASY
Tags: Spanning trees

Graph algorithms

Data structures

Mathematics


Solutions:
import sys
input = sys.stdin.readline
for _ in range(int(input())):
	n = int(input())
	c = mx = i = int()
	for x in input().split():
		mx = max(mx, int(x))
		if mx == i + 1:
			c += 1
		i += 1
	print(c)


import sys
import math
from collections import deque
input = sys.stdin.readline

def multiple():
	a = map(int, input().split())
	return a

def array():
	a = input().split()
	return a

def intarray():
	a = list(map(int, input().split()))
	return a

def smaller(a1, a2):
	n = len(a1)
	for i in range(n):
		if a1[i] < a2[i]:
			return True
		elif a1[i] > a2[i]:
			return False
	return False

def solution():
	n = int(input())
	a = intarray()
	maxsofar = a[0]
	smallcountpossible = a[0] - 1
	ans = 1
	for i in range(1, n):
		if smallcountpossible <= 0:
			ans += 1
		if a[i] > maxsofar:
			smallcountpossible += a[i] - maxsofar - 1
			maxsofar = a[i]
		else:
			smallcountpossible -= 1
	print(ans)
	return
t = int(input())
for _ in range(t):
	solution()


from collections import defaultdict, deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, itertools, math
sys.setrecursionlimit(10 ** 5)
input = sys.stdin.readline
sqrt = math.sqrt

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

def LF():
	return list(map(float, input().split()))

def LI_():
	return list(map(lambda x: int(x) - 1, input().split()))

def II():
	return int(input())

def IF():
	return float(input())

def S():
	return input().rstrip()

def LS():
	return S().split()

def IR(n):
	return [II() for _ in range(n)]

def LIR(n):
	return [LI() for _ in range(n)]

def FR(n):
	return [IF() for _ in range(n)]

def LFR(n):
	return [LI() for _ in range(n)]

def LIR_(n):
	return [LI_() for _ in range(n)]

def SR(n):
	return [S() for _ in range(n)]

def LSR(n):
	return [LS() for _ in range(n)]
mod = 1000000007
inf = 10000000000.0

def solve():
	t = II()
	for _ in range(t):
		n = II()
		p = LI()
		ans = [0, 0]
		nn = 0
		for pi in p:
			if ans[0] == ans[1]:
				ans[0] = pi
				nn += 1
			if ans[0] < pi:
				ans[0] = pi
			ans[1] += 1
		print(nn)
	return
solve()


import sys
import random

def solve():
	inp = sys.stdin.readline
	n = int(inp())
	p = list(map(int, inp().split()))
	w = [False] * (n + 2)
	ans = 0
	m = 0
	j = 1
	for i in p:
		m = max(m, i)
		w[i] = True
		while w[j]:
			j += 1
		if j > m:
			ans += 1
	print(ans)

def main():
	for i in range(int(sys.stdin.readline())):
		solve()
main()


import sys
from typing import List

def sol(perm: List[int]) -> int:
	max_ = 0
	counter = 0
	for (idx, num) in enumerate(perm):
		max_ = max(max_, num)
		if max_ == idx + 1:
			counter += 1
	return counter

def main():
	inp = sys.stdin.readlines()
	rest = inp[1:]
	permutations = rest[1::2]
	permutations = [[int(num) for num in line.split()] for line in permutations]
	for perm in permutations:
		print(sol(perm))
main()


import sys
input = sys.stdin.readline

def solve(n, p):
	stack = []
	for i in range(n):
		curr = (p[i], p[i])
		while stack and stack[-1][1] > curr[0]:
			(a, b) = stack.pop()
			curr = (min(a, curr[0]), max(b, curr[1]))
		stack.append(curr)
	print(len(stack))
for _ in range(int(input())):
	n = int(input())
	p = list(map(int, input().split()))
	solve(n, p)


from sys import stdin
input = stdin.readline
for _ in range(int(input())):
	n = int(input())
	p = [int(i) for i in input().split()]
	c = 0
	mx = 0
	for i in range(n):
		mx = max(mx, p[i])
		if mx == i + 1:
			c = c + 1
	print(c)


import sys
input = sys.stdin.readline
for j in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	cnt = 0
	x = 0
	for i in range(n):
		x = max(x, a[i])
		if x == i + 1:
			cnt += 1
	print(cnt)


import sys
input = sys.stdin.readline
t = int(input())
for i in range(t):
	n = int(input())
	p = [int(x) for x in input().split(' ')]
	ma = 0
	res = 0
	for j in range(n):
		ma = max(ma, p[j])
		if ma == j + 1:
			res += 1
	print(res)


import sys

def solution(array):
	array.insert(0, 0)
	max_num = 0
	num_comps = -1
	for (i, pi) in enumerate(array):
		max_num = max(pi, max_num)
		if i == max_num:
			num_comps += 1
	print(num_comps)
	return
input = sys.stdin.read().splitlines()
t = int(input[0])
offset = 1
for test in range(t):
	n = input[2 * test + offset]
	array = input[2 * test + offset + 1].split(' ')
	array = [int(e) for e in array]
	solution(array)


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	n = int(input())
	p = list(map(int, input().split()))
	cnt = 0
	currmax = p[0]
	for i in range(n):
		if p[i] > currmax:
			currmax = p[i]
		if currmax == i + 1:
			cnt += 1
	print(cnt)


import sys
input = sys.stdin.readline
for j in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	count = 0
	x = 0
	for i in range(n):
		x = max(x, arr[i])
		if x == i + 1:
			count += 1
	print(count)


import sys
input = sys.stdin.readline
for case in range(int(input())):
	length = int(input())
	line = list(map(int, input().split()))
	maxx = 0
	maxs = []
	for i in line:
		if i > maxx:
			maxx = i
		maxs.append(maxx)
	minx = 999999
	mins = []
	for i in line[::-1]:
		if i < minx:
			minx = i
		mins.append(minx)
	mins.reverse()
	quantity = 0
	for i in range(1, length):
		if line[i] > line[i - 1] and maxs[i - 1] < mins[i]:
			quantity += 1
	print(quantity + 1)


from sys import stdin
input = stdin.readline
for _ in range(int(input())):
	n = int(input())
	p = [int(i) for i in input().split()]
	op = p.index(1)
	np = p.index(n)
	if op > np:
		print(1)
		continue
	c = 0
	mx = 0
	for i in range(n):
		mx = max(mx, p[i])
		if mx == i + 1:
			c = c + 1
	print(c)


import sys
input = sys.stdin.readline

def solve(n, p):
	v = -float('inf')
	cnt = 0
	for i in range(n):
		v = max(v, p[i])
		if v == i + 1:
			cnt += 1
	print(cnt)
for _ in range(int(input())):
	n = int(input())
	p = list(map(int, input().split()))
	solve(n, p)


from collections import Counter, defaultdict, deque
import bisect
from sys import stdin, stdout
from itertools import repeat
import math

def inp(force_list=False):
	re = list(map(int, input().split()))
	if len(re) == 1 and (not force_list):
		return re[0]
	return re

def inst():
	return input().strip()

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

def my_main():
	kase = inp()
	pans = []
	for kk in range(kase):
		n = inp()
		da = inp(True)
		st = []
		for i in range(n):
			st.append((da[i], da[i]))
			while len(st) >= 2 and (st[-2][0] < st[-1][0] < st[-2][1] or st[-1][0] < st[-2][0] < st[-1][1] or da[i] < st[-2][1]):
				(x, y) = st.pop()
				(a, b) = st.pop()
				st.append((min(x, a), max(y, b)))
		pans.append(str(len(st)))
	print('\n'.join(pans))
my_main()


n = int(input())
killer = []
for i in range(n):
	k = int(input())
	cnt = 0
	ans = 0
	mylist = list(map(int, input().split()))
	for (x, i) in enumerate(mylist, 1):
		ans = max(ans, i)
		if x < ans:
			pass
		else:
			cnt = cnt + 1
	killer.append(cnt)
print(*killer, sep='\n')


import sys
input = sys.stdin.readline

def solve(n, p):
	nextSmaller = [-1] * n
	stack = []
	for i in range(n):
		while stack and p[stack[-1]] > p[i]:
			nextSmaller[stack.pop()] = i
		stack.append(i)
	intervals = []
	visited = set()
	for i in range(n):
		if i in visited:
			continue
		idx = i
		visited.add(idx)
		while nextSmaller[idx] != -1:
			idx = nextSmaller[idx]
			visited.add(idx)
		intervals.append((i, idx, p[i], p[idx]))
	count = 1
	(ps, pe, pmax, pmin) = intervals[0]
	for i in range(1, len(intervals)):
		(cs, ce, cmax, cmin) = intervals[i]
		if ps <= cs <= pe:
			(ps, pe) = (min(ps, cs), max(pe, ce))
			(pmax, pmin) = (max(pmax, cmax), min(pmin, cmin))
		elif pmax > cmin:
			(ps, pe) = (min(ps, cs), max(pe, ce))
			(pmax, pmin) = (max(pmax, cmax), min(pmin, cmin))
		else:
			count += 1
			(ps, pe, pmax, pmin) = (cs, ce, cmax, cmin)
	print(count)
	return
for _ in range(int(input())):
	n = int(input())
	p = list(map(int, input().split()))
	solve(n, p)


t = int(input())
results = []
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	m = 0
	n = 0
	c = 0
	for a in arr:
		if a > m:
			n = n + (a - m - 1)
			m = a
		else:
			n -= 1
		if n == 0:
			c += 1
	results.append(c)
for r in results:
	print(r)


l1 = []
t = int(input())
for test in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	ma = c = 0
	for i in range(n):
		ma = max(ma, l[i])
		if ma == i + 1:
			c += 1
	l1.append(c)
print(*l1, sep='\n')


p = []
a = int(input())
for i in range(a):
	e = int(input())
	q = list(map(int, input().split()))
	g = list()
	h = q[0] - 1
	x = q[0]
	for j in range(1, e):
		if q[j] < x:
			h -= 1
		elif h != 0:
			h += q[j] - x - 1
			x = q[j]
		else:
			g.append(x)
			h = q[j] - x - 1
			x = q[j]
	g.append(0)
	p.append(g)
for i in p:
	print(len(i))


sI = lambda : input()
iI = lambda : int(input())
mI = lambda : map(int, input().split())
lI = lambda : list(mI())
from math import ceil
from collections import defaultdict
anss = []
for _ in range(iI()):
	n = iI()
	a = lI()
	cm = a[0]
	vis = 0
	ans = 0
	for i in range(n):
		cm = max(cm, a[i])
		vis += 1
		if vis == cm:
			ans += 1
	anss.append(ans)
for i in anss:
	print(i)


import sys
t = int(sys.stdin.readline())
for iiii in range(t):
	n = sys.stdin.readline()
	n = int(n)
	ar = sys.stdin.readline().split(' ')
	ar = [int(i) for i in ar]
	idx = dict()
	for i in range(len(ar)):
		idx[ar[i]] = i
	ans = []
	now = []
	for i in ar:
		if len(now) == 0 or now[0] > i:
			now.append(i)
		else:
			ans.append(now)
			now = [i]
	if len(now) != 0:
		ans.append(now)
	count = len(ans)
	for i in range(len(ans)):
		now = ans[i]
		len_now = len(now)
		need = now[0] - idx[now[0]]
		if len_now < need:
			count -= 1
	print(count)


T = int(input())
rt = []

def root(i):
	while i != rt[i]:
		rt[i] = rt[rt[i]]
		i = rt[i]
	return i

def merge(a, b):
	(a, b) = (root(a), root(b))
	if a == b:
		return
	rt[b] = a
res = []
while T:
	N = int(input())
	vals = [*map(int, input().split())]
	rt = [*range(N)]
	st = []
	for (i, val) in enumerate(vals):
		if not st or st[-1][0] < val:
			st.append((val, i))
		else:
			last = st[-1]
			while len(st) and st[-1][0] > val:
				merge(st[-1][1], i)
				st.pop()
			st.append(last)
	res.append(len(set([root(i) for i in rt])))
	T -= 1
print(*res, sep='\n')


class UnionFind(object):

	def __init__(self, n):
		self.parent = [-1] * n

	def find(self, x):
		if self.parent[x] != x:
			self.parent[x] = self.find(self.find(self.parent[x]))
		return self.parent[x]

	def union(self, x, y):
		(root_x, root_y) = (self.find(x), self.find(y))
		if root_x == root_y:
			return
		self.parent[root_x] = root_y

	def isconnected(self, x, y):
		return self.find(x) == self.find(y)

def main():
	t = int(input())
	ans = []
	for _ in range(t):
		n = int(input())
		p = [int(s) for s in input().split()]
		stack = []
		UF = UnionFind(n)
		for i in range(n):
			UF.parent[i] = i
			stack.append((p[i], p[i], i))
			while len(stack) >= 2 and stack[-1][0] < stack[-2][1]:
				(min_, max_) = (min(stack[-1][0], stack[-2][0]), max(stack[-1][1], stack[-2][1]))
				stack.pop()
				stack[-1] = (min_, max_, stack[-1][2])
				UF.union(i, stack[-1][2])
		res = 0
		for i in range(n):
			if UF.parent[i] == i:
				res += 1
		ans.append(res)
	print('\n'.join([str(num) for num in ans]))
main()


t = int(input())
import sys
while t > 0:
	t = t - 1
	n = int(input())
	a = [int(x) for x in sys.stdin.readline().split()]
	ans = [a[0]]
	for i in range(1, n):
		x = ans[-1]
		while len(ans) > 0 and ans[-1] > a[i]:
			ans.pop()
		ans.append(max(a[i], x))
	print(len(ans))


def solveC(a):
	if len(a) == 1:
		return 1
	intervals = []
	max = a[0]
	min = a[0]
	for value in a[1:]:
		if value > max:
			intervals.append([min, max])
			max = value
			min = value
		if value < min:
			min = value
	intervals.append([min, max])
	intervals = sorted(intervals, key=lambda x: x[0])
	merged = mergeIntervals(intervals)
	return len(merged)

def mergeIntervals(intervals):
	result = []
	current = intervals[0]
	for interval in intervals[1:]:
		if current[1] > interval[0]:
			current[0] = min(current[0], interval[0])
			current[1] = max(current[1], interval[1])
		else:
			result.append(current)
			current = interval
	result.append(current)
	return result
num_tests = int(input().split()[0])
for t in range(num_tests):
	n = int(input().split()[0])
	a = [int(x) for x in input().split()]
	print(solveC(a))


from collections import deque
nbTest = int(input())

def mergeTop(q):
	if len(q) < 2:
		return 0
	top = q.pop()
	top2 = q.pop()
	if top2[0] > top[1]:
		new = [max(top2[0], top[0]), min(top[1], top2[1])]
		q.append(new)
		return 1
	else:
		q.append(top2)
		q.append(top)
		return 0
for blak in range(nbTest):
	nbN = int(input())
	q = deque()
	heads = []
	maxHead = 0
	for sNum in input().split():
		num = int(sNum)
		toAdd = [num, num]
		q.append(toAdd)
		while mergeTop(q):
			continue
	print(len(q))


import sys

def run():
	_ = int(input())
	arr = list(map(int, input().split()))
	ans = list()
	for v in arr:
		w = v
		while len(ans) and ans[-1] > v:
			w = max(w, ans.pop())
		ans.append(w)
	print(len(ans))

def main():
	t = int(input())
	for _ in range(t):
		run()
main()


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	p_i = 0
	ma = l[0]
	c = 1
	for i in range(1, n):
		if l[i] > ma:
			if l[p_i] <= i:
				c += 1
			p_i = i
			ma = l[i]
	print(c)


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

def li():
	return list(map(int, input().split()))
t = ii()
while t:
	t -= 1
	n = ii()
	a = li()
	if n == 1:
		print(1)
	elif n == 2:
		if a[0] == 2:
			print(1)
		else:
			print(2)
	else:
		curr = 0
		ans = 0
		for i in range(n):
			if a[i] > curr:
				curr = a[i]
			if curr == i + 1:
				ans += 1
		print(ans)


from sys import maxsize
for t in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	p_i = 0
	max = l[0]
	component = 1
	for i in range(1, n):
		if l[i] > max:
			if l[p_i] <= i:
				component += 1
			p_i = i
			max = l[i]
	print(component)


cases = int(input())
for _ in range(cases):
	num = int(input())
	arr = list(map(int, input().split()))
	sor = sorted(arr)
	if arr == sor:
		print(num)
	elif arr[0] == num:
		print(1)
	else:
		mx = 0
		ans = 0
		st = set()
		prev = 1
		for n in arr:
			if n > mx:
				if not st:
					ans += 1
				mx = n
				for i in range(prev, mx):
					st.add(i)
				prev = mx + 1
			else:
				st.remove(n)
		print(ans)


T = int(input())
for _ in range(T):
	N = int(input())
	arr = list(map(int, input().split()))
	answer = 0
	goal = 0
	cnt = 0
	for n in arr:
		if n > goal:
			if cnt == goal:
				answer += 1
			goal = n
		cnt += 1
	print(answer)


from audioop import reverse

def crush(stack):
	while len(stack) > 1 and stack[-1][0] < stack[-2][1]:
		a = stack.pop()
		b = stack.pop()
		stack.append([min(a[0], b[0]), max(a[1], b[1])])
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	if list(sorted(a, reverse=True)) == a:
		print(1)
		continue
	stack = []
	for i in range(n):
		if len(stack) > 0 and a[i] < stack[-1][1]:
			stack[-1][0] = min(stack[-1][0], a[i])
			stack[-1][1] = max(stack[-1][1], a[i])
			crush(stack)
		else:
			stack.append([a[i], a[i]])
	print(len(stack))


def solve():
	input()
	A = [int(x) for x in input().split()]
	mx = 0
	ret = 0
	left = set()
	for x in A:
		if x > mx:
			if not left:
				ret += 1
			for y in range(mx + 1, x):
				left.add(y)
			mx = x
		if x in left:
			left.remove(x)
	return ret
t = int(input())
for _ in range(t):
	print(solve())


n = int(input())
for e in range(n):
	t = int(input())
	l = list(map(int, input().split()))
	i = 1
	s = [l[0]]
	while i < len(l):
		if l[i] > s[-1]:
			s.append(l[i])
			i += 1
		else:
			c = 0
			while s != [] and l[i] < s[-1]:
				if c == 0:
					q = s.pop()
				else:
					s.pop()
				c += 1
			s.append(q)
			i += 1
	print(len(s))


t = int(input())
for _ in range(t):
	n = int(input())
	P = [int(pi) for pi in input().split()]
	stack = list()
	for p in P:
		stack.append((p, p))
		while len(stack) >= 2:
			(max1, min1) = stack.pop()
			(max2, min2) = stack.pop()
			if max2 > min1:
				stack.append((max(max1, max2), min(min1, min2)))
			else:
				stack.append((max2, min2))
				stack.append((max1, min1))
				break
	print(len(stack))


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	mex = arr[0]
	used = 1
	cnt = 0
	for i in range(1, n):
		if mex == used:
			cnt += 1
		mex = max(mex, arr[i])
		used += 1
	print(cnt + 1)


def main():
	t = int(input())
	for _ in range(t):
		n = int(input())
		p = [int(s) for s in input().split()]
		stack = []
		for i in range(n):
			stack.append((p[i], p[i]))
			while len(stack) >= 2 and stack[-1][0] < stack[-2][1]:
				min_ = min(stack[-1][0], stack[-2][0])
				max_ = max(stack[-1][1], stack[-2][1])
				stack.pop()
				stack[-1] = (min_, max_)
		print(len(stack))
main()


t = int(input())
for _ in range(t):
	n = int(input())
	p = input().split()
	runningMax = [0] * n
	runningMin = [n] * n
	runningMax[0] = int(p[0])
	runningMin[n - 1] = int(p[n - 1])
	for i in range(1, n):
		runningMax[i] = max(runningMax[i - 1], int(p[i]))
		runningMin[n - i - 1] = min(runningMin[n - i], int(p[n - i - 1]))
	components = 1
	for i in range(1, n):
		if runningMin[i] > runningMax[i - 1]:
			components += 1
	print(components)


for _ in range(int(input())):
	n = int(input())
	numbers = list(map(int, input().split(' ')))
	cnt = 0
	mx = 0
	for (i, nb) in enumerate(numbers):
		mx = max(mx, nb)
		if mx == i + 1:
			cnt += 1
	print(cnt)


for __ in range(int(input())):
	n = int(input())
	ar = list(map(int, input().split()))
	num = 0
	ans = 0
	for i in range(n):
		if ar[i] > num:
			num = ar[i]
		if i + 1 == num:
			ans += 1
	print(ans)


from sys import maxsize

def ga():
	return list(map(int, input().split()))
for _ in range(int(input())):
	n = int(input())
	arr = ga()
	stack = []
	for i in arr:
		stack.append((i, i))
		while len(stack) >= 2:
			(mi1, ma1) = stack[-1]
			(mi2, ma2) = stack[-2]
			if mi1 < ma2:
				stack.pop()
				stack.pop()
				stack.append((min(mi1, mi2), max(ma1, ma2)))
			else:
				break
	print(len(stack))


import math
from collections import *

def solve():
	n = int(input())
	a = [int(i) for i in input().split()]
	s = 0
	c = 0
	for i in range(n):
		s += a[i]
		if s == (i + 1) * (i + 2) // 2:
			c += 1
	print(c)
t = int(input())
for _ in range(t):
	solve()


import collections
from math import ceil, gcd, sqrt, log
INF = float('inf')
mod = 1000000007

def solve():
	n = int(input())
	A = list(map(int, input().split()))
	stack = [A[0]]
	for i in range(1, n):
		top = stack[-1]
		while stack and stack[-1] > A[i]:
			stack.pop()
		stack.append(max(top, A[i]))
	print(len(stack))
t = int(input())
while t != 0:
	solve()
	t -= 1


for _ in range(int(input())):
	n = int(input())
	z = list(map(int, input().split()))
	mx = 0
	x = [[z[0], z[0]]]
	for i in range(1, n):
		if z[i] < x[-1][1]:
			if z[i] < x[-1][0]:
				x[-1][0] = z[i]
		else:
			x.append([z[i], z[i]])
		while len(x) > 1 and x[-1][0] < x[-2][1]:
			(a, b) = (x.pop(), x.pop())
			x.append([min(a[0], b[0]), max(a[1], b[1])])
	print(len(x))


def main_function():
	test_cases = range(int(input()))
	for test_case in test_cases:
		n = int(input())
		a = [int(i) for i in input().split(' ')]
		roots = [a[0]]
		for i in range(1, len(a)):
			max_val = roots[-1]
			if a[i] > max_val:
				roots.append(a[i])
			else:
				while len(roots) > 0 and roots[-1] > a[i]:
					roots.pop()
				roots.append(max_val)
		print(len(roots))
main_function()


import bisect

def solve(a, n):
	res = 1
	nodes = [0] * n
	nodes[0] = a[0]
	for i in range(1, n):
		idx = bisect.bisect(nodes, a[i], 0, res)
		if idx == res:
			nodes[idx] = a[i]
		else:
			nodes[idx] = nodes[res - 1]
		res = idx + 1
	print(res)
	return
t = int(input())
for i in range(1, t + 1):
	n = int(input())
	a = list(map(int, input().split()))
	solve(a, n)


n = int(input())
for i in range(n):
	tam = int(input())
	lista = list(map(int, input().split()))
	maior = 0
	soma = 0
	contagem = 0
	for j in range(tam):
		if lista[j] > maior:
			if contagem == maior:
				soma += 1
				maior = lista[j]
			else:
				maior = lista[j]
		contagem += 1
	print(soma)


from math import *
from math import factorial as fact, comb as ncr
from bisect import bisect_left as bl
from bisect import bisect_right as br
from collections import Counter as ctr
from collections import deque as dq
from array import array
inp = lambda : int(input())
li = lambda : list(map(int, input().split()))
lb = lambda : list(map(int, input()))
ls = lambda : list(input())
arr = lambda a: array('i', a)
bi = lambda n: bin(n).replace('0b', '')
yn = lambda f: print('NYOE S'[f::2])

def solve(__=1):
	for _ in range(__):
		n = inp()
		a = li()
		c = 0
		m = 0
		for (i, x) in enumerate(a):
			m = max(m, x)
			if m == i + 1:
				c += 1
		print(c)
solve(inp())


for _ in range(int(input())):
	n = int(input())
	lis = list(map(int, input().split()))
	ans = 0
	cur = 1
	val = lis[0]
	for i in range(1, n):
		if val == cur:
			ans += 1
		val = max(val, lis[i])
		cur += 1
	print(ans + 1)


T = int(input())
for i in range(T):
	n = int(input())
	inpt = [int(x) for x in input().split(' ')]
	stack = []
	for ele in reversed(inpt):
		if len(stack) > 0:
			mins = float('inf')
			while 1:
				if len(stack) > 0:
					if stack[-1] < ele:
						pe = stack.pop()
						mins = min(pe, mins)
					else:
						pe = min(mins, ele)
						stack.append(pe)
						break
				else:
					pe = min(mins, ele)
					stack.append(pe)
					break
		else:
			stack.append(ele)
	print(len(stack))


t = int(input())
while t:
	n = int(input())
	p = list(map(int, input().split()))
	m = 0
	ans = 0
	for i in range(n):
		if p[i] >= m:
			if i >= m:
				ans = ans + 1
			m = p[i]
	print(ans)
	t = t - 1


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().strip().split()))
	ma = l[0]
	co = 0
	for i in range(n):
		if l[i] > ma:
			ma = l[i]
		if ma == i + 1:
			co += 1
	print(co)


for _ in range(int(input())):
	n = int(input())
	p = list(map(int, input().split()))
	cnt = 0
	currmax = p[0]
	for i in range(n):
		if p[i] > currmax:
			currmax = p[i]
		if currmax == i + 1:
			cnt += 1
			if i + 1 < n:
				currmax = p[i + 1]
	print(cnt)


t = int(input())
for _ in range(t):
	_ = int(input())
	arr = list(map(int, input().split()))
	(maxs, max_maxs) = ([], 0)
	for i in arr:
		max_yet = i
		while maxs and i < maxs[-1]:
			max_yet = max(max_yet, maxs.pop())
		maxs.append(max_yet)
	print(len(maxs))


def func():
	n = int(input())
	l = list(map(int, input().split()))
	comp = 0
	(high, cnt) = (0, 0)
	for i in l:
		if high == cnt:
			high = i
			comp += 1
		high = max(high, i)
		cnt += 1
	return comp
t = int(input())
for i in range(t):
	print(func())


T = int(input())
for z in range(0, T):
	N = int(input())
	A = list(map(int, input().split()))
	count = 1
	Max = A[0]
	res = 0
	if count == Max:
		res += 1
	for i in range(1, N):
		count += 1
		if Max < A[i]:
			Max = A[i]
		if count == Max:
			res += 1
	print(res)


def solve():
	n = int(input())
	a = list(map(int, input().split()))
	(mx, ans) = (0, 0)
	for i in range(n):
		mx = max(mx, a[i])
		ans += mx == i + 1
	print(ans)
tst = int(input())
while tst:
	solve()
	tst -= 1


def main():
	T = int(input())
	for k in range(T):
		n = int(input())
		array = list(map(int, input().split(' ')))
		(mx, count) = (0, 0)
		for i in range(len(array)):
			mx = max(array[i], mx)
			if mx == i + 1:
				count += 1
		print(count)
main()


T = int(input())
for _ in range(T):
	n = int(input())
	a = []
	m = 0
	c = 0
	a = [int(x) for x in input().split(' ')]
	i = 0
	for j in a:
		m = max(m, j)
		if m == i + 1:
			c += 1
		i += 1
	print(c)


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	c = 0
	s = 0
	for j in range(n):
		s = s + arr[j]
		if s == (j + 1) * (j + 2) // 2:
			c += 1
	print(c)


import sys

def get_ints():
	return map(int, sys.stdin.readline().strip().split())

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

def main():
	for _ in range(int(input())):
		n = int(input())
		ls = get_ls()
		ans = mx = 0
		for i in range(len(ls)):
			mx = max(ls[i], mx)
			if mx == i + 1:
				ans += 1
		print(ans)
main()


t = int(input())
for _ in range(t):
	n = int(input())
	p = [int(i) for i in input().strip().split()]
	count = 0
	free_to_go = 0
	for i in range(n):
		if p[i] > i + 1:
			free_to_go = max(free_to_go, p[i])
		if i + 1 >= free_to_go:
			count += 1
	print(count)


t = int(input())
for j in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	count = 0
	x = 0
	for i in range(n):
		x = max(x, a[i])
		if x == i + 1:
			count += 1
	print(count)


for i in range(int(input())):
	n = int(input())
	p = list(map(int, input().split()))
	j = 0
	otv = 1
	while j < n:
		if j == 0:
			k = p[0] - 1
			tekysh_k = p[0]
			naibolosh_v_k = p[0]
		elif tekysh_k == naibolosh_v_k:
			otv += 1
			k = p[j] - 1 - j
			tekysh_k = p[j]
			naibolosh_v_k = p[j]
		else:
			k = naibolosh_v_k - j
			tekysh_k = naibolosh_v_k
			j -= 1
		while k > 0:
			j += 1
			if p[j] < tekysh_k:
				k -= 1
			elif p[j] > naibolosh_v_k:
				naibolosh_v_k = p[j]
		j += 1
	print(otv)


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

def solve():
	(n,) = read_nums()
	perm = read_nums()
	res = 0
	cur_sum = 0
	target_sum = 0
	for i in range(n):
		cur_sum += perm[i]
		target_sum += i + 1
		if cur_sum == target_sum:
			res += 1
	return res

def main():
	(t,) = read_nums()
	for _ in range(t):
		print(solve())
main()


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	c = 0
	mi = 1000000000.0
	ma = -1000000000.0
	for i in range(n):
		if a[i] > ma:
			ma = a[i]
		if a[i] < mi:
			mi = a[i]
		if mi == 1 and ma == i + 1:
			c += 1
	print(c)


t = int(input())
for i in range(0, t):
	n = int(input())
	lis = list(map(int, input().split()))
	s = 0
	ans = 0
	for j in range(0, n):
		s = s + lis[j]
		if s == (j + 1) * (j + 2) // 2:
			ans = ans + 1
	print(ans)


from math import ceil, log10
import bisect
import math
from collections import defaultdict
from itertools import groupby
from collections import defaultdict, Counter
from heapq import heappop, heappush
from collections import deque
from re import A
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	ans = 0
	maximum = 0
	for i in range(n):
		maximum = max(maximum, arr[i])
		if maximum == i + 1:
			ans += 1
	print(ans)


for _ in range(int(input())):
	n = int(input())
	l1 = [int(i) for i in input().split()]
	st = []
	for i in range(n):
		if st:
			if l1[i] < st[-1][0]:
				if l1[i] < st[-1][1]:
					st[-1][1] = l1[i]
			else:
				st.append([l1[i], l1[i]])
		else:
			st.append([l1[i], l1[i]])
	ans = 1
	p = st[-1][1]
	for i in range(len(st) - 2, -1, -1):
		if st[i][0] > p:
			p = min(p, st[i][1])
			continue
		else:
			ans += 1
			p = st[i][1]
	print(ans)


t = int(input())
while t > 0:
	t = t - 1
	n = int(input())
	a = input().split()
	for i in range(0, n):
		a[i] = int(a[i])
	ans = [a[0]]
	for i in range(1, n):
		x = ans[-1]
		while len(ans) > 0 and ans[-1] > a[i]:
			ans.pop()
		ans.append(max(a[i], x))
	print(len(ans))


for i in range(int(input())):
	n = int(input())
	P = [int(k) for k in input().split()]
	d = 1
	z = P[0]
	m = 0
	for k in range(n):
		if z < P[k]:
			z = P[k]
		if d == z:
			m += 1
		d += 1
	print(m)