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).

You are given a permutation of $1,2,\dots,n$, $[a_1,a_2,\dots,a_n]$. For integers $i$, $j$ such that $1\le i<j\le n$, define $\operatorname{mn}(i,j)$ as $\min\limits_{k=i}^j a_k$, and define $\operatorname{mx}(i,j)$ as $\max\limits_{k=i}^j a_k$.

Let us build an undirected graph of $n$ vertices, numbered $1$ to $n$. For every pair of integers $1\le i<j\le n$, if $\operatorname{mn}(i,j)=a_i$ and $\operatorname{mx}(i,j)=a_j$ both holds, or $\operatorname{mn}(i,j)=a_j$ and $\operatorname{mx}(i,j)=a_i$ both holds, add an undirected edge of length $1$ between vertices $i$ and $j$.

In this graph, find the length of the shortest path from vertex $1$ to vertex $n$. We can prove that $1$ and $n$ will always be connected via some path, so a shortest path always exists.


-----Input-----

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

The first line of each test case contains one integer $n$ ($1\le n\le 2.5\cdot 10^5$).

The second line of each test case contains $n$ integers $a_1$, $a_2$, $\ldots$, $a_n$ ($1\le a_i\le n$). It's guaranteed that $a$ is a permutation of $1$, $2$, $\dots$, $n$.

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


-----Output-----

For each test case, print a single line containing one integer — the length of the shortest path from $1$ to $n$.


-----Examples-----

Input
5
1
1
2
1 2
5
1 4 2 3 5
5
2 1 5 3 4
10
7 4 8 1 6 10 3 5 2 9
Output
0
1
1
4
6


-----Note-----

The following are illustrations of constructed graphs in example test cases.

the constructed graph in test case 1

the constructed graph in test case 2

the constructed graph in test case 3

the constructed graph in test case 4

the constructed graph in test case 5

Difficulty: HARD
Tags: Shortest paths

Constructive algorithms

Sorting

Greedy algorithms

Divide and conquer

Data structures
Skill types: Sorting

Data structures

Greedy algorithms

Starter code:

Solutions:
for _ in range(int(input())):
	n = int(input())
	k = [None] * n
	for (i, x) in enumerate(map(int, input().split())):
		k[x - 1] = i
	count = 0
	(i, j, d) = (0, n - 1, k[0])
	while d != 0:
		while k[j] > d:
			j -= 1
		d = k[j]
		count += 1
		if d == 0:
			break
		while k[i] > d:
			i += 1
		d = k[i]
		count += 1
	(i, j, d) = (0, n - 1, k[0])
	while d != n - 1:
		while k[j] < d:
			j -= 1
		d = k[j]
		count += 1
		if d == n - 1:
			break
		while k[i] < d:
			i += 1
		d = k[i]
		count += 1
	print(count)


import sys

def solve():
	inp = sys.stdin.readline
	n = int(inp())
	a = list(map(int, inp().split()))
	pos = [None] * (n + 1)
	for i in range(n):
		pos[a[i]] = i
	st1 = [(-1, n)]
	st2 = [(n + 1, n)]
	next_below = [None] * n
	next_above = [None] * n
	for i in range(n - 1, -1, -1):
		v = a[i]
		while st1[-1][0] > v:
			st1.pop()
		next_below[i] = st1[-1][1]
		st1.append((v, i))
		while st2[-1][0] < v:
			st2.pop()
		next_above[i] = st2[-1][1]
		st2.append((v, i))
	i = 0
	ans = 0
	while i + 1 < n:
		v = a[i]
		if v < a[i + 1]:
			next = next_below[i]
			j = next_above[i]
			while next_above[j] < next:
				j = next_above[j]
		else:
			next = next_above[i]
			j = next_below[i]
			while next_below[j] < next:
				j = next_below[j]
		i = j
		ans += 1
	print(ans)

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


import sys
input = sys.stdin.readline
t = int(input())
for _ in range(t):
	n = int(input())
	(*a,) = map(int, input().split())
	if n == 1:
		print(0)
		continue
	fmin = []
	fmax = []
	cmin = n
	imin = 1
	cmax = 1
	imax = 1
	for i in range(n):
		v = a[i]
		if v <= cmin:
			cmin = v
			imin = i
		if v >= cmax:
			cmax = v
			imax = i
		fmin += [imin]
		fmax += [imax]
	bmin = []
	bmax = []
	cmin = n
	imin = 1
	cmax = 1
	imax = 1
	for i in range(n - 1, -1, -1):
		v = a[i]
		if v <= cmin:
			cmin = v
			imin = i
		if v >= cmax:
			cmax = v
			imax = i
		bmin += [imin]
		bmax += [imax]
	idx = fmax[n - 1]
	bmin = bmin[::-1]
	bmax = bmax[::-1]
	tlist = ((fmin, fmax), (bmin, bmax))
	res = 0
	ismax = 0
	isback = 0
	idx1 = idx
	while idx1 != 0:
		res += 1
		idx1 = tlist[isback][ismax][idx1]
		ismax ^= 1
	ismax = 0
	isback = 1
	idx1 = idx
	while idx1 != n - 1:
		res += 1
		idx1 = tlist[isback][ismax][idx1]
		ismax ^= 1
	print(res)


def solve(a, start, small):
	n = len(a)
	count = 0
	while start != n - 1:
		count += 1
		if small:
			start = max(range(start, n), key=a.__getitem__)
			small = False
		else:
			start = min(range(start, n), key=a.__getitem__)
			small = True
	return count
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	if n == 1:
		print(0)
		continue
	k = [None] * n
	for (i, x) in enumerate(a):
		k[x - 1] = i
	count = 0
	i = 0
	j = n - 1
	d = k[0]
	while True:
		while k[j] > d:
			j -= 1
		d = k[j]
		count += 1
		if i == j:
			break
		while k[i] > d:
			i += 1
		d = k[i]
		count += 1
		if i == j:
			break
	i = 0
	j = n - 1
	d = k[0]
	while True:
		while k[j] < d:
			j -= 1
		d = k[j]
		count += 1
		if i == j:
			break
		while k[i] < d:
			i += 1
		d = k[i]
		count += 1
		if i == j:
			break
	print(count - 2)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	a = [0] + a
	ans = 0
	pos = [0] * (n + 1)
	pmx = [0] * (n + 1)
	pmn = [10 ** 9] * (n + 1)
	smx = [0] * (n + 1)
	smn = [10 ** 9] * (n + 1)
	for i in range(1, 1 + n):
		pmn[i] = min(pmn[i - 1], a[i])
		pmx[i] = max(pmx[i - 1], a[i])
		pos[a[i]] = i
	smn[-1] = a[-1]
	smx[-1] = a[-1]
	for i in range(n - 1, 0, -1):
		smn[i] = min(smn[i + 1], a[i])
		smx[i] = max(smx[i + 1], a[i])
	i = pos[1]
	lst = 0
	while i != 1:
		if lst == 0:
			x = pmx[i - 1]
			i = pos[x]
			lst = 1
		else:
			x = pmn[i - 1]
			i = pos[x]
			lst = 0
		ans += 1
	i = pos[1]
	lst = 0
	while i != n:
		if lst == 0:
			x = smx[i + 1]
			i = pos[x]
			lst = 1
		else:
			x = smn[i + 1]
			i = pos[x]
			lst = 0
		ans += 1
	print(ans)