Read problem statements in [Hindi], [Bengali], [Mandarin Chinese], [Russian], and [Vietnamese] as well.

JJ has a magical sequence $A_{1}, A_{2}, \ldots, A_{N}$. The group of high magicians Sed wants to buy this sequence from him. They calculate its cost as follows:
Choose a subarray of length atleast $2$, i.e. a contiguous subsequence $A_{l}, A_{l+1}, \ldots, A_{r}$ such that $1 ≤ l < r ≤ N$.
The cost is the difference between the largest and the second largest element in this subarray (note that if there is more than one element with the maximum value, the cost is $0$).

Clearly, the cost is not uniquely determined, but depends on the choice of the subarray in the first step. JJ is careful, so he wants to find the number of different possible amounts of money he can obtain, i.e. the size of the set of all possible costs for all valid choices of this subarray.

------  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-seperated integers $A_{1}, A_{2}, \ldots, A_{N}$.

------  Output ------
For each test case, print a single line containing one integer — the number of possible costs.

------  Constraints  ------
$1 ≤ T ≤ 10^{5}$
$2 ≤ N ≤ 10^{5}$
$1 ≤ A_{i} ≤ 10^{9}$ for each valid $i$
the sum of $N$ over all test cases does not exceed $10^{6}$

------  Subtasks ------
Subtask #1 (30 points): the sum of $N$ over all test cases does not exceed $5 \cdot 10^{3}$

Subtask #2 (70 points): original constraints

----- Sample Input 1 ------ 
2

2

1 2

3

5 1 3
----- Sample Output 1 ------ 
1

2
----- explanation 1 ------ 
Example case 1: $[1, 2]$ is the only possible subarray that satisfies $l < r$. For this subarray, the cost is $2 - 1 = 1$. The set of all possible costs is $\{1\}$ and the answer is its size, $1$.

Example case 2: There are three subarray that can be chosen: $[5, 1]$, $[1, 3]$ and $[5, 1, 3]$. The costs for them are $4$, $2$ and $2$ respectively. Hence, the set of possible costs is $\{2, 4\}$ and the answer is its size, $2$.

Difficulty: VERY_HARD
Tags: Constructive algorithms

Data structures

Ad-hoc
Skill types: Data structures

Starter code:

Solutions:
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	stack = []
	res = []
	for i in range(n):
		while len(stack) != 0 and stack[-1] <= arr[i]:
			temp = stack.pop()
			res.append(abs(arr[i] - temp))
		if len(stack) != 0:
			res.append(abs(stack[-1] - arr[i]))
		stack.append(arr[i])
	print(len(list(set(res))))


T = int(input())
for i in range(T):
	n = int(input())
	arr = list(map(int, input().split()))
	ans = []
	stack = []
	for i in range(n):
		if not stack:
			stack.append(arr[i])
		elif stack[-1] > arr[i]:
			ans.append(stack[-1] - arr[i])
			stack.append(arr[i])
		else:
			while stack and stack[-1] <= arr[i]:
				p = stack.pop()
				ans.append(arr[i] - p)
			if stack:
				ans.append(abs(arr[i] - stack[-1]))
			stack.append(arr[i])
	print(len(list(set(ans))))


for _ in range(int(input())):
	b = int(input())
	a = list(map(int, input().split()))
	stack = []
	result = []
	for i in range(b):
		while stack and stack[-1] <= a[i]:
			tmp = stack.pop()
			result.append(abs(a[i] - tmp))
		if stack:
			result.append(stack[-1] - a[i])
		stack.append(a[i])
	print(len(list(set(result))))


for _ in range(int(input())):
	n = int(input())
	a = [int(i) for i in input().split()][:n]
	(st, result) = ([], [])
	for i in range(n):
		while st and st[-1] <= a[i]:
			tmp = st.pop()
			result.append(a[i] - tmp)
		if st:
			result.append(st[-1] - a[i])
		st.append(a[i])
	print(len(list(set(result))))


from sys import stdin, stdout
from collections import deque
nmbr = lambda : int(input())
lst = lambda : list(map(int, input().split()))
for _ in range(nmbr()):
	n = nmbr()
	a = lst()
	biggest = deque()
	ngr = [n] * n
	for i in range(n - 1, -1, -1):
		v = a[i]
		while biggest and v > a[biggest[-1]]:
			biggest.pop()
		if biggest:
			ngr[i] = biggest[-1]
		biggest.append(i)
	smallest = deque()
	nsr = [n] * n
	for i in range(n - 1, -1, -1):
		v = a[i]
		while smallest and a[smallest[-1]] > v:
			smallest.pop()
		if smallest:
			nsr[i] = smallest[-1]
		smallest.append(i)
	biggest = deque()
	ngl = [-1] * n
	for i in range(n):
		v = a[i]
		while biggest and v > a[biggest[-1]]:
			biggest.pop()
		if biggest:
			ngl[i] = biggest[-1]
		biggest.append(i)
	smallest = deque()
	nsl = [-1] * n
	for i in range(n):
		v = a[i]
		while smallest and a[smallest[-1]] > v:
			smallest.pop()
		if smallest:
			nsl[i] = smallest[-1]
		smallest.append(i)
	ans = set()
	for i in range(n):
		v = a[i]
		if ngl[i] != -1:
			ans.add(a[ngl[i]] - v)
		if ngr[i] != n:
			ans.add(a[ngr[i]] - v)
	print(len(ans))


def NGE(arr, n):
	st = []
	ans = []
	for i in range(n):
		while len(st) > 0 and st[-1] <= arr[i]:
			ans.append(arr[i] - st[-1])
			st.pop()
		st.append(arr[i])
	return ans
tcs = int(input())
for _ in range(tcs):
	n = int(input())
	a = list(map(int, input().split()))
	a1 = NGE(a, n)
	a2 = NGE(a[::-1], n)[::-1]
	an = set(a1 + a2)
	print(len(an))


import sys, math, itertools, random, bisect
from collections import defaultdict
INF = 10 ** 18

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

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

def input():
	return sys.stdin.readline().strip()
mod = 10 ** 9 + 7
test = 1
test = int(input())
for _ in range(test):
	(n,) = get_ints()
	a = get_array()
	ans = set()
	(left, right) = ([-1] * n, [-1] * n)
	st = []
	for i in range(n):
		while st and st[-1] < a[i]:
			st.pop()
		if st:
			left[i] = st[-1]
		st.append(a[i])
	st = []
	for i in range(n - 1, -1, -1):
		while st and st[-1] < a[i]:
			st.pop()
		if st:
			right[i] = st[-1]
		st.append(a[i])
	for i in range(n):
		if left[i] != -1:
			ans.add(left[i] - a[i])
		if right[i] != -1:
			ans.add(right[i] - a[i])
	print(len(ans))


import sys
intinp = lambda : int(input())

def listinp(func=int):
	return list(map(func, input().split()))

def nsepline(n, func=str):
	return [func(input()) for _ in range(n)]

def printlist(li, glue=' '):
	return glue.join(list(map(str, li)))

def fop(s, end='\n'):
	sys.stdout.write(str(s) + end)

def fip():
	return sys.stdin.readline().strip()
fintinp = lambda : int(fip())

def flistinp(func=int):
	return list(map(func, fip().split()))

def fnsepline(n, func=str):
	return [func(fip()) for _ in range(n)]
test_cases = fintinp()
for _ in range(test_cases):
	n = fintinp()
	l = flistinp()
	anss = set()
	mx_ltr = [-1] * n
	st = []
	for i in range(n):
		while st and l[st[-1]] <= l[i]:
			mx_ltr[st.pop()] = l[i]
		st.append(i)
	st.clear()
	mx_rtl = [-1] * n
	l.reverse()
	for i in range(n):
		while st and l[st[-1]] <= l[i]:
			mx_rtl[st.pop()] = l[i]
		st.append(i)
	mx_rtl.reverse()
	l.reverse()
	for i in range(n):
		if mx_ltr[i] != -1:
			anss.add(mx_ltr[i] - l[i])
		if mx_rtl[i] != -1:
			anss.add(mx_rtl[i] - l[i])
	print(len(anss))


t = int(input())
for test in range(t):
	n = int(input())
	l = [int(j) for j in input().split()]
	lm = [-1 for j in range(n)]
	rm = [-1 for j in range(n)]
	st = []
	for i in range(n):
		if len(st) == 0:
			st.append(i)
		else:
			while l[st[-1]] <= l[i]:
				z = st.pop()
				rm[z] = l[i]
				if len(st) == 0:
					break
			st.append(i)
	l = l[::-1]
	st = []
	for i in range(n):
		if len(st) == 0:
			st.append(i)
		else:
			while l[st[-1]] <= l[i]:
				z = st.pop()
				lm[z] = l[i]
				if len(st) == 0:
					break
			st.append(i)
	l = l[::-1]
	lm = lm[::-1]
	ans = 0
	z = set()
	for i in range(n):
		if lm[i] != -1:
			if lm[i] - l[i] not in z:
				z.add(lm[i] - l[i])
		if rm[i] != -1:
			if rm[i] - l[i] not in z:
				z.add(rm[i] - l[i])
	print(len(z))


from sys import stdin, stdout
input = stdin.readline
t = int(input())
for _ in range(t):
	n = int(input())
	a = [int(x) for x in input().split()]
	nge = [-1 for i in range(n)]
	pge = [-1 for i in range(n)]
	stack1 = []
	stack2 = []
	for i in range(n):
		if not len(stack1):
			stack1.append(i)
		elif a[i] < a[stack1[-1]]:
			stack1.append(i)
		else:
			while 1:
				if not len(stack1):
					break
				if a[stack1[-1]] <= a[i]:
					nge[stack1.pop()] = a[i]
				else:
					break
			stack1.append(i)
	a = a[::-1]
	for i in range(n):
		if not len(stack2):
			stack2.append(i)
		elif a[i] < a[stack2[-1]]:
			stack2.append(i)
		else:
			while 1:
				if not len(stack2):
					break
				if a[stack2[-1]] <= a[i]:
					pge[n - stack2.pop() - 1] = a[i]
				else:
					break
			stack2.append(i)
	a = a[::-1]
	s = set()
	for i in range(n):
		if nge[i] != -1:
			s.add(nge[i] - a[i])
		if pge[i] != -1:
			s.add(pge[i] - a[i])
	print(len(s))


for test in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	ans = set()
	st = [a[0]]
	for i in range(1, n):
		pp = st[-1]
		while pp < a[i]:
			ans.add(a[i] - pp)
			st.pop()
			if len(st):
				pp = st[-1]
			else:
				pp = -1
				break
		if pp != -1:
			st.append(pp)
			ans.add(pp - a[i])
		st.append(a[i])
	print(len(ans))


t = int(input())
for _ in range(t):
	n = int(input())
	a = [int(i) for i in input().split()]
	s = set()
	leftst = [a[0]]
	for i in range(1, len(a)):
		while leftst and a[i] >= leftst[-1]:
			leftst.pop()
		if leftst:
			s.add(leftst[-1] - a[i])
		leftst.append(a[i])
	rightst = [a[len(a) - 1]]
	for i in range(len(a) - 2, -1, -1):
		while rightst and a[i] > rightst[-1]:
			rightst.pop()
		if rightst:
			s.add(rightst[-1] - a[i])
		rightst.append(a[i])
	print(len(s))


def answer():
	r = [-1] * n
	s = []
	for i in range(n):
		if s == []:
			s.append(i)
			continue
		while s != [] and a[s[-1]] <= a[i]:
			r[s[-1]] = a[i]
			s.pop()
		s.append(i)
	l = [-1] * n
	s = []
	for i in range(n - 1, -1, -1):
		if s == []:
			s.append(i)
			continue
		while s != [] and a[s[-1]] <= a[i]:
			l[s[-1]] = a[i]
			s.pop()
		s.append(i)
	ans = set()
	for i in range(n):
		if r[i] != -1:
			ans.add(r[i] - a[i])
		if l[i] != -1:
			ans.add(l[i] - a[i])
	return len(ans)
for T in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	print(answer())


import sys, io, os, time
from collections import defaultdict
from collections import Counter
from collections import deque
from itertools import combinations
from itertools import permutations
import bisect, math, heapq
alphabet = 'abcdefghijklmnopqrstuvwxyz'

def ceil(num, denom):
	return (num + denom - 1) // denom
input = sys.stdin.readline
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	st = []
	pairs = set()
	st.append(a[0])
	for i in range(1, n):
		while len(st) and a[i] > st[-1]:
			pairs.add(abs(st[-1] - a[i]))
			st.pop()
		if len(st) != 0:
			pairs.add(abs(min(st[-1], a[i]) - max(st[-1], a[i])))
		st.append(a[i])
	print(len(pairs))


from sys import stdin
input = stdin.readline

def pairs(arr):
	st = []
	ans = set()
	st.append(arr[0])
	for i in range(1, len(arr)):
		while len(st) != 0 and arr[i] > st[-1]:
			ans.add(arr[i] - st[-1])
			st.pop()
		if len(st) != 0:
			ans.add(abs(arr[i] - st[-1]))
		st.append(arr[i])
	return len(ans)
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	print(pairs(a))


def solve(arr):
	st = list()
	pairs = set()
	st.append(arr[0])
	for i in range(1, len(arr)):
		while len(st) != 0 and arr[i] > st[-1]:
			pairs.add(abs(st[-1] - arr[i]))
			st.pop()
		if len(st) != 0:
			pairs.add(abs(min(st[-1], arr[i]) - max(st[-1], arr[i])))
		st.append(arr[i])
	return len(pairs)
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	print(solve(a))


def pairs(arr):
	st = []
	l = []
	st.append(arr[0])
	for i in range(1, len(arr)):
		while len(st) != 0 and arr[i] > st[-1]:
			l.append(arr[i] - st[-1])
			st.pop()
		if len(st) != 0:
			val1 = min(st[-1], arr[i])
			val2 = max(st[-1], arr[i])
			l.append(val2 - val1)
		st.append(arr[i])
	return len(set(l))
t = int(input())
while t:
	t -= 1
	n = int(input())
	l = list(map(int, input().split()))
	ans = pairs(l)
	print(ans)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	st = []
	pairs = set()
	st.append(a[0])
	for i in range(1, n):
		while len(st) and a[i] >= st[-1]:
			pairs.add(abs(st[-1] - a[i]))
			st.pop()
		if len(st) != 0:
			pairs.add(abs(st[-1] - a[i]))
		st.append(a[i])
	print(len(pairs))


from sys import stdin, stdout
stdin.readline

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

def it():
	return int(stdin.readline().strip())

def pairs(arr):
	stack = []
	pairs = []
	stack.append(arr[0])
	for i in range(1, len(arr)):
		while len(stack) != 0 and arr[i] > stack[-1]:
			pairs.append([stack[-1], arr[i]])
			stack.pop()
		if len(stack):
			pairs.append([min(stack[-1], arr[i]), max(stack[-1], arr[i])])
		stack.append(arr[i])
	s = set()
	for i in pairs:
		s.add(abs(i[0] - i[1]))
	return s
for _ in range(it()):
	n = it()
	l = mp()
	print(len(pairs(l)))


t = int(input())
for _ in range(t):
	n = int(input())
	ls = list(map(int, input().split()))
	set_diff = set()
	stack = [ls[0]]
	new_ls = ls[1:]
	for i in new_ls:
		while stack and i >= stack[-1]:
			set_diff.add(i - stack[-1])
			stack.pop()
		stack.append(i)
	rev_ls = ls[::-1]
	stack = [rev_ls[0]]
	new_ls = rev_ls[1:]
	for i in new_ls:
		while stack and i >= stack[-1]:
			set_diff.add(i - stack[-1])
			stack.pop()
		stack.append(i)
	print(len(set_diff))


from collections import defaultdict, OrderedDict, Counter
from sys import stdin, stdout
from bisect import bisect_left, bisect_right
from queue import Queue, PriorityQueue
from heapq import heapify, heappop, heappush
from statistics import median, mean
from math import gcd, sqrt, floor, factorial, ceil, log2, log10, log
import fractions
import copy
from copy import deepcopy
import sys
import io
sys.setrecursionlimit(10 ** 8)
import math
import os
import bisect
import collections
mod = pow(10, 9) + 7
import random
from random import random, randint, randrange
from time import time

def ncr(n, r, p=mod):
	num = den = 1
	for i in range(r):
		num = num * (n - i) % p
		den = den * (i + 1) % p
	return num * pow(den, p - 2, p) % p

def normalncr(n, r):
	r = min(r, n - r)
	count = 1
	for i in range(n - r, n + 1):
		count *= i
	for i in range(1, r + 1):
		count //= i
	return count
inf = float('inf')
adj = defaultdict(set)
visited = defaultdict(int)

def addedge(a, b):
	adj[a].add(b)
	adj[b].add(a)

def bfs(v):
	q = Queue()
	q.put(v)
	visited[v] = 1
	while q.qsize() > 0:
		s = q.get_nowait()
		print(s)
		for i in adj[s]:
			if visited[i] == 0:
				q.put(i)
				visited[i] = 1

def dfs(v, visited):
	if visited[v] == 1:
		return
	visited[v] = 1
	print(v)
	for i in adj[v]:
		dfs(i, visited)

def reverse_bisect_right(a, x, lo=0, hi=None):
	if lo < 0:
		raise ValueError('lo must be non-negative')
	if hi is None:
		hi = len(a)
	while lo < hi:
		mid = (lo + hi) // 2
		if x > a[mid]:
			hi = mid
		else:
			lo = mid + 1
	return lo

def reverse_bisect_left(a, x, lo=0, hi=None):
	if lo < 0:
		raise ValueError('lo must be non-negative')
	if hi is None:
		hi = len(a)
	while lo < hi:
		mid = (lo + hi) // 2
		if x >= a[mid]:
			hi = mid
		else:
			lo = mid + 1
	return lo

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

def get_str_list_in_int():
	return [int(i) for i in list(input())]

def get_str_list():
	return list(input())

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

def input_int():
	return int(input())

def matrix(a, b):
	return [[0 for i in range(b)] for j in range(a)]

def swap(a, b):
	return (b, a)

def find_gcd(l):
	a = l[0]
	for i in range(len(l)):
		a = gcd(a, l[i])
	return a

def is_prime(n):
	sqrta = int(sqrt(n))
	for i in range(2, sqrta + 1):
		if n % i == 0:
			return 0
	return 1

def prime_factors(n):
	sqrta = int(sqrt(n))
	for i in range(2, sqrta + 1):
		if n % i == 0:
			return [i] + prime_factors(n // i)
	return [n]

def p(a):
	if type(a) == str:
		print(a + '\n')
	else:
		print(str(a) + '\n')

def ps(a):
	if type(a) == str:
		print(a)
	else:
		print(str(a))

def kth_no_not_div_by_n(n, k):
	return k + (k - 1) // (n - 1)

def forward_array(l):
	stack = []
	forward = [0] * n
	for i in range(len(l) - 1, -1, -1):
		while len(stack) and l[stack[-1]] < l[i]:
			stack.pop()
		if len(stack) == 0:
			forward[i] = len(l)
		else:
			forward[i] = stack[-1]
		stack.append(i)
	return forward

def backward_array(l):
	stack = []
	backward = [0] * n
	for i in range(len(l)):
		while len(stack) and l[stack[-1]] < l[i]:
			stack.pop()
		if len(stack) == 0:
			backward[i] = -1
		else:
			backward[i] = stack[-1]
		stack.append(i)
	return backward
nc = 'NO'
yc = 'YES'
ns = 'No'
ys = 'Yes'
t = int(input())
for i in range(t):
	n = int(input())
	l = get_list()
	dict = defaultdict(int)
	forward = forward_array(l)
	backward = backward_array(l)
	for i in range(n):
		j = forward[i]
		if j != n:
			dict[l[j] - l[i]] = 1
	for i in range(n):
		j = backward[i]
		if j != -1:
			dict[l[j] - l[i]] = 1
	print(len(dict))


import heapq

def gcd(a, b):
	while b:
		(a, b) = (b, a % b)
	return a

def prime(n):
	arr = [True] * (n + 1)
	arr[0] = False
	arr[1] = False
	for i in range(n + 1):
		if arr[i]:
			for j in range(i * i, n + 1, i):
				arr[j] = False
	return arr[n]

def nextLargerElement(arr):
	st = []
	ans = [-1] * len(arr)
	for i in range(len(arr)):
		while st and arr[st[-1]] <= arr[i]:
			ans[st.pop()] = arr[i]
		st.append(i)
	return ans
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	ans = set()
	ansr = nextLargerElement(arr)
	ansl = nextLargerElement(arr[::-1])[::-1]
	for i in range(len(arr)):
		if ansr[i] != -1:
			ans.add(ansr[i] - arr[i])
		if ansl[i] != -1:
			ans.add(ansl[i] - arr[i])
	print(len(ans))


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	stack = []
	s = set()
	for i in l:
		f = 0
		while len(stack) > 0 and f == 0:
			if stack[-1] > i:
				f = 1
				break
			x = stack.pop()
			s.add(i - x)
		stack.append(i)
	j = n - 1
	stack = []
	while j > -1:
		i = l[j]
		f = 0
		while len(stack) > 0 and f == 0:
			if stack[-1] > i:
				f = 1
				break
			x = stack.pop()
			s.add(i - x)
		stack.append(i)
		j = j - 1
	sys.stdout.write(str(len(s)) + '\n')


from os import path
from io import BytesIO, IOBase
import sys
from heapq import heappush, heappop
from functools import cmp_to_key as ctk
from collections import deque, Counter, defaultdict as dd
from bisect import bisect, bisect_left, bisect_right, insort, insort_left, insort_right
from itertools import permutations
from datetime import datetime
from math import ceil, sqrt, log, gcd

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

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

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

def li():
	return list(mi())
abc = 'abcdefghijklmnopqrstuvwxyz'
mod = 1000000007
inf = float('inf')
vow = ['a', 'e', 'i', 'o', 'u']
(dx, dy) = ([-1, 1, 0, 0], [0, 0, 1, -1])

def bo(i):
	return ord(i) - ord('0')
file = 1

def ceil(a, b):
	return (a + b - 1) // b

def solve():
	for _ in range(ii()):
		n = ii()
		a = li()
		s = set()
		for i in range(2):
			nxt_gre = [0] * n
			mx = 0
			st = []
			for i in range(n):
				while len(st) > 0 and st[-1] < a[i]:
					st.pop()
				if len(st) > 0:
					s.add(st[-1] - a[i])
				while len(st) > 0 and st[-1] == a[i]:
					st.pop()
				st.append(a[i])
			a.reverse()
		print(len(s))
if file:
	if path.exists('tmp/input.txt'):
		sys.stdin = open('tmp/input.txt', 'r')
		sys.stdout = open('tmp/output.txt', 'w')
	else:
		input = sys.stdin.readline
solve()


def solve():
	n = int(input())
	a = list(map(int, input().split()))
	(s, ans, stack) = (set(), 0, [])
	for num in a:
		while len(stack) and stack[-1] < num:
			stack.pop()
		if len(stack):
			diff = abs(num - stack[-1])
			if diff not in s:
				ans += 1
				s.add(diff)
		stack.append(num)
	stack.clear()
	for num in reversed(a):
		while len(stack) and stack[-1] < num:
			stack.pop()
		if len(stack):
			diff = abs(num - stack[-1])
			if diff not in s:
				ans += 1
				s.add(diff)
		stack.append(num)
	print(ans)
tc = int(input())
for i in range(tc):
	solve()


import math, sys
from collections import defaultdict, Counter, deque
from bisect import bisect_left, bisect_right
INF = float('inf')
MOD = int(1000000000.0) + 7
MAX = int(2000000.0) + 1

def solve():
	n = int(input())
	arr = array()
	ans = set()
	q = deque()
	left = [-1 for i in range(n)]
	right = [-1 for i in range(n)]
	for i in range(n):
		while q and q[-1][0] < arr[i]:
			q.pop()
		if q:
			left[i] = q[-1][1]
		q.append((arr[i], i))
	q = deque()
	for i in range(n - 1, -1, -1):
		while q and q[-1][0] < arr[i]:
			q.pop()
		if q:
			right[i] = q[-1][1]
		q.append((arr[i], i))
	for i in range(n):
		tmp = left[i]
		if tmp != -1:
			ans.add(abs(arr[i] - arr[tmp]))
		tmp = right[i]
		if tmp != -1:
			ans.add(abs(arr[tmp] - arr[i]))
	print(len(ans))

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

def gcd(a, b):
	while b:
		(a, b) = (b, a % b)
	return a

def input():
	return sys.stdin.readline().rstrip('\n').strip()

def print(*args, sep=' ', end='\n'):
	first = True
	for arg in args:
		if not first:
			sys.stdout.write(sep)
		sys.stdout.write(str(arg))
		first = False
	sys.stdout.write(end)
primes = [1 for i in range(MAX)]

def sieve():
	global primes
	primes[0] = primes[1] = 0
	i = 2
	while i <= MAX ** 0.5:
		j = i * i
		while primes[i] and j < MAX:
			if j % i == 0:
				primes[j] = 0
			j += i
		i += 1

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

def array():
	return list(vars())
main()


def sedMax(N, a):
	s = list()
	k = set()
	left = [-1 for _ in range(N)]
	right = [-1 for _ in range(N)]
	for i in range(N):
		while len(s) > 0 and s[-1] < a[i]:
			s.pop()
		if len(s) == 0:
			left[i] = ' '
		else:
			left[i] = s[-1]
		s.append(a[i])
	s = list()
	for i in range(N - 1, -1, -1):
		while len(s) > 0 and s[-1] < a[i]:
			s.pop()
		if len(s) == 0:
			right[i] = ' '
		else:
			right[i] = s[-1]
		s.append(a[i])
	for i in range(N):
		if left[i] != ' ':
			k.add(left[i] - a[i])
		if right[i] != ' ':
			k.add(right[i] - a[i])
	return len(k)
for _ in range(int(input())):
	N = int(input())
	A = list(map(int, input().split()))
	print(sedMax(N, A))


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	costs = set()
	for i in range(2):
		stack = []
		for j in range(n):
			while len(stack) > 0 and stack[-1] <= a[j]:
				costs.add(a[j] - stack[-1])
				stack.pop()
			stack.append(a[j])
		a.reverse()
	print(len(costs))


t = int(input())
while t > 0:
	n = int(input())
	l = list(map(int, input().split()))
	ans = []
	for j in range(0, 2):
		stack = []
		for i in range(0, n):
			while len(stack) != 0 and stack[-1] <= l[i]:
				ans.append(l[i] - stack[-1])
				stack.pop()
			stack.append(l[i])
		l.reverse()
	print(len(set(ans)))
	t = t - 1


from math import *
from bisect import *
from collections import *
from random import *
from decimal import *
import sys
input = sys.stdin.readline

def inp():
	return int(input())

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

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

def ma():
	return map(int, input().split())
t = inp()
while t:
	t -= 1
	n = inp()
	a = lis()
	st = [a[0]]
	f = set()
	for i in range(1, n):
		while st and a[i] > st[-1]:
			f.add(abs(a[i] - st[-1]))
			st.pop()
		if st:
			f.add(abs(st[-1] - a[i]))
		st.append(a[i])
	print(len(f))


import sys
input = lambda : sys.stdin.readline().rstrip('\r\n')
inp = lambda : list(map(int, sys.stdin.readline().rstrip('\r\n').split()))
mod = 10 ** 9 + 7
Mod = 998244353
INF = float('inf')
tc = 1
(tc,) = inp()
for _ in range(tc):
	(n,) = inp()
	a = inp()
	left = []
	stack = []
	for i in range(n):
		while stack and stack[-1] < a[i]:
			stack.pop()
		if stack:
			left.append(stack[-1])
		else:
			left.append(-1)
		stack.append(a[i])
	stack = []
	right = []
	for i in range(n - 1, -1, -1):
		while stack and stack[-1] < a[i]:
			stack.pop()
		if stack:
			right.append(stack[-1])
		else:
			right.append(-1)
		stack.append(a[i])
	right.reverse()
	s = set()
	for i in range(n):
		if left[i] != -1:
			s.add(abs(left[i] - a[i]))
		if right[i] != -1:
			s.add(abs(right[i] - a[i]))
	print(len(s))


def pairs(arr):
	st = []
	pairs = []
	d = 0
	st.append(arr[0])
	for i in range(1, len(arr)):
		while len(st) != 0 and arr[i] > st[-1]:
			pairs.append((st[-1], arr[i]))
			st.pop()
		if len(st) != 0:
			pairs.append((min(st[-1], arr[i]), max(st[-1], arr[i])))
		st.append(arr[i])
	return pairs

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
t = int(input())
while t > 0:
	n = int(input())
	l = [int(x) for x in input().split()]
	k = pairs(l)
	d = len(k)
	c = []
	for i in range(d):
		c.append(abs(k[i][0] - k[i][1]))
	print(len(set(c)))
	t -= 1


def pairs(arr):
	st = []
	pairs = []
	st.append(arr[0])
	for i in range(1, len(arr)):
		while len(st) != 0 and arr[i] > st[-1]:
			pairs.append((st[-1], arr[i]))
			st.pop()
		if len(st) != 0:
			pairs.append((min(st[-1], arr[i]), max(st[-1], arr[i])))
		st.append(arr[i])
	return pairs
for _ in range(int(input())):
	N = int(input())
	vec = list(map(int, input().split()))
	sts = set()
	st = pairs(vec)
	for x in st:
		sts.add(abs(x[0] - x[1]))
	print(len(sts))


def pairs(arr):
	st = []
	pairs = []
	st.append(arr[0])
	for i in range(1, len(arr)):
		while len(st) != 0 and arr[i] > st[-1]:
			pairs.append(abs(st[-1] - arr[i]))
			st.pop()
		if len(st) != 0:
			pairs.append(min(abs(st[-1] - arr[i]), abs(st[-1] - arr[i])))
		st.append(arr[i])
	return pairs
from collections import Counter
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	ans = pairs(l)
	ans = set(ans)
	print(len(ans))


def pairs(arr):
	st = []
	pairs = []
	st.append(arr[0])
	for i in range(1, len(arr)):
		while len(st) != 0 and arr[i] > st[-1]:
			pairs.append((st[-1], arr[i]))
			st.pop()
		if len(st) != 0:
			pairs.append((min(st[-1], arr[i]), max(st[-1], arr[i])))
		st.append(arr[i])
	return pairs
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	save = pairs(l)
	s = set()
	for i in save:
		s.add(i[1] - i[0])
	print(len(s))


def myfunc(arr):
	stack = []
	group = set()
	stack.append(arr[0])
	for i in range(1, len(arr)):
		while len(stack) != 0 and arr[i] > stack[-1]:
			group.add(abs(stack[-1] - arr[i]))
			stack.pop()
		if len(stack) != 0:
			group.add(abs(stack[-1] - arr[i]))
		stack.append(arr[i])
	return len(group)
for gg in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	s = myfunc(l)
	print(s)


def pairs(arr):
	st = []
	pairs = []
	st.append(arr[0])
	for i in range(1, len(arr)):
		while len(st) != 0 and arr[i] > st[-1]:
			pairs.append((st[-1], arr[i]))
			st.pop()
		if len(st) != 0:
			pairs.append((min(st[-1], arr[i]), max(st[-1], arr[i])))
		st.append(arr[i])
	return pairs

def main():
	T = int(input())
	for _ in range(T):
		n = int(input())
		A = list(map(int, input().split()))
		G = {}
		cnt = 0
		par = pairs(A)
		for i in par:
			(x, y) = i
			if abs(x - y) not in G:
				G[abs(x - y)] = 1
				cnt = cnt + 1
		print(cnt)
main()


for i in range(int(input())):
	N = int(input())
	arr = list((int(i) for i in input().split()))
	cost = {}
	j = 1
	stack = [arr[0]]
	while j <= N - 1:
		while stack != []:
			if stack[-1] <= arr[j]:
				cost[arr[j] - stack.pop()] = 1
			else:
				cost[stack[-1] - arr[j]] = 1
				break
		stack.append(arr[j])
		j += 1
	print(len(cost))


from sys import stdin, stdout
input = stdin.readline
from random import sample
t = int(input())
from collections import Counter
from math import sqrt, ceil

def pairs(arr):
	st = []
	pairs = []
	st.append(arr[0])
	for i in range(1, len(arr)):
		while len(st) != 0 and arr[i] > st[-1]:
			pairs.append((st[-1], arr[i]))
			st.pop()
		if len(st) != 0:
			pairs.append((min(st[-1], arr[i]), max(st[-1], arr[i])))
		st.append(arr[i])
	return pairs

def f(arr, i, j, d, dist):
	if i == j:
		return
	nn = max(arr[i:j])
	for tl in range(i, j):
		if arr[tl] == nn:
			dist[tl] = d
			f(arr, i, tl, d + 1, dist)
			f(arr, tl + 1, j, d + 1, dist)

def ps(n):
	cp = 0
	while n % 2 == 0:
		n = n // 2
		cp += 1
	for ps in range(3, ceil(sqrt(n)) + 1, 2):
		while n % ps == 0:
			n = n // ps
			cp += 1
	if n != 1:
		return False
	return True

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

def factorials(n, r):
	slr = n
	dpr = r
	qlr = 1
	qs = 1
	mod = 10 ** 9 + 7
	for ip in range(n - r + 1, n + 1):
		qlr = qlr * ip % mod
	for ij in range(1, r + 1):
		qs = qs * ij % mod
	ans = qlr * modInverse(qs) % mod
	return ans

def modInverse(b):
	qr = 10 ** 9 + 7
	return pow(b, qr - 2, qr)
tt = [xa ** 3 for xa in range(0, 10 ** 4 + 1)]
qq = set(tt)
for jj in range(t):
	n = int(input())
	arr = [int(x) for x in input().strip().split()]
	brr = pairs(arr)
	skp = set()
	for xy in brr:
		skp.add(xy[1] - xy[0])
	print(len(skp))
	continue
	l = 0
	while l <= n - 2:
		maxi = arr[l]
		smaxi = arr[l]
		for ij in range(l + 1, n):
			if arr[ij] >= maxi:
				smaxi = maxi
				maxi = arr[ij]
			elif arr[ij] >= smaxi or ij == l + 1:
				smaxi = arr[ij]
			skp.add(maxi - smaxi)
		l += 1
	print(len(skp))


def solve(A, n):
	possibleValues = set()
	prevGreaterElemIndices = [-1] * n
	for i in range(1, n):
		possibleValues.add(abs(A[i] - A[i - 1]))
		if A[i] > A[i - 1]:
			index = i - 1
			while index >= 0 and prevGreaterElemIndices[index] != -1 and (A[prevGreaterElemIndices[index]] <= A[i]):
				possibleValues.add(abs(A[i] - A[prevGreaterElemIndices[index]]))
				index = prevGreaterElemIndices[index]
			if prevGreaterElemIndices[index] != -1:
				possibleValues.add(abs(A[i] - A[prevGreaterElemIndices[index]]))
			prevGreaterElemIndices[i] = prevGreaterElemIndices[index]
		elif A[i] == A[i - 1]:
			prevGreaterElemIndices[i] = prevGreaterElemIndices[i - 1]
		else:
			prevGreaterElemIndices[i] = i - 1
	return len(possibleValues)
t = int(input())
for tc in range(t):
	n = int(input())
	A = list(map(int, input().split()))
	result = solve(A, n)
	print(result)


from sys import stdin

def input():
	return stdin.readline()
for _ in range(int(input())):
	n = int(input())
	nums = list(map(int, input().split()))
	temp_list = [nums[0]]
	sum_set = set()
	for i in range(1, n):
		if nums[i] < temp_list[-1]:
			sum_set.add(temp_list[-1] - nums[i])
			temp_list.append(nums[i])
		else:
			while temp_list and nums[i] >= temp_list[-1]:
				sum_set.add(nums[i] - temp_list.pop())
			if temp_list:
				sum_set.add(temp_list[-1] - nums[i])
			temp_list.append(nums[i])
	print(len(sum_set))


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	ans = set()
	for arr in [arr, arr[::-1]]:
		s = []
		for i in arr:
			while s and s[-1] <= i:
				ans.add(i - s.pop(-1))
			s.append(i)
	print(len(ans))


from collections import deque
for _ in range(int(input())):
	input()
	arr = list(map(int, input().split()))
	d = deque([arr[0]])
	s = set()
	for i in range(1, len(arr)):
		if len(d) < 2:
			s.add(abs(d[-1] - arr[i]))
			d.append(arr[i])
		else:
			while len(d) > 1 and d[-1] >= d[0]:
				d.popleft()
			while len(d) > 1 and arr[i] >= d[-1]:
				s.add(arr[i] - d.pop())
			while len(d) > 1 and d[0] <= arr[i]:
				d.popleft()
			s.add(abs(d[-1] - arr[i]))
			d.append(arr[i])
	print(len(s))


I = lambda : list(map(int, input().split()))
(t,) = I()
for _ in range(t):
	(n,) = I()
	l = I()
	st = set()
	stack = []
	for i in range(n):
		while stack and stack[-1] < l[i]:
			st.add(abs(l[i] - stack.pop()))
		stack.append(l[i])
		try:
			cr = len(stack)
			st.add(abs(stack[0] - stack[1]))
			st.add(abs(stack[-1] - stack[-2]))
		except:
			pass
	cr = len(stack)
	if cr > 1:
		st.add(abs(stack[0] - stack[1]))
		st.add(abs(stack[-1] - stack[-2]))
	print(len(st))