The *beauty* value of an array is defined as the difference between the largest and second largest elements of the array. Note that the largest and second largest elements can have the same value in case of duplicates.

For example, *beauty* value of [2, 5, 3, 1] = 5 - 3 = 2 and *beauty* value of [7, 6, 7] = 7 - 7 = 0 

You are given an array A of length N. Your task is to find the total number of distinct *beauty* values among all *subarrays* of A having length greater than 1.

Note that, a subarray is obtained by deleting some (possibly zero) elements from the beginning and some (possibly zero) elements from the end of the array.

------ Input Format ------ 

- The first line of input will contain a single integer T, denoting the number of test cases.
- Each test case consists of two lines of input.
- The first line of each test case contains a single integer N — the size of the array.
- The second line contains N space-separated numbers - A_{1}, A_{2},\ldots ,A_{N}, the elements of the array.

------ Output Format ------ 

For each test case, output a single line, the total number of distinct beauty among all *subarrays* of A having length greater than 1.

------ Constraints ------ 

$1 ≤ T ≤ 10^{4}$
$2 ≤ N ≤ 2 \cdot 10^{5}$
$1 ≤ A_{i} ≤ 10^{9}$
- Sum of $N$ over all test cases does not exceed $2 \cdot 10^{5}$.

----- Sample Input 1 ------ 
4
2
1 1
3
4 2 1
4
8 1 7 2
5
6 9 4 2 1

----- Sample Output 1 ------ 
1
2
4
4

----- explanation 1 ------ 
Test case $1$: The only subarray is $[1,1]$ whose beauty is $0$. Thus, there is only $1$ distinct value of beauty.

Test case $2$: The subarrays are $[4,2], [2,1],$ and $[4,2,1]$ having beauty $2, 1,$ and $2$ respectively. There are $2$ distinct values of beauty.

Test case $3$: The unique values of beauty are $7,1,6,$ and $5$.

Test case $4$: The unique values of beauty are $3,5,2,$ and $1$.

Difficulty: HARD
Tags: Data structures
Skill types: Data structures

Starter code:

Solutions:
t = int(input())
for i in range(t):
	n = int(input())
	ar = list(map(int, input().split()))
	l = set()
	v = [ar[0]]
	for i in range(1, n):
		while v and v[-1] <= ar[i]:
			l.add(ar[i] - v[-1])
			v.pop()
		if v:
			l.add(v[-1] - ar[i])
		v.append(ar[i])
	print(len(l))


import sys, heapq, bisect, math
from functools import lru_cache
from collections import defaultdict, Counter, deque
from itertools import permutations, combinations, product

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

def singleLineArrInt():
	return [int(n) for n in _input().split(' ')]

def singleLineArrStr():
	return [s for s in _input().split(' ')]

def solve(n, nums):
	right = [-1] * n
	stack = []
	for i in range(n):
		while stack and nums[stack[-1]] <= nums[i]:
			right[stack.pop()] = i
		stack.append(i)
	left = [-1] * n
	stack = []
	for i in range(n - 1, -1, -1):
		while stack and nums[stack[-1]] <= nums[i]:
			left[stack.pop()] = i
		stack.append(i)
	res = set()
	for i in range(n):
		if left[i] != -1:
			res.add(nums[left[i]] - nums[i])
		if right[i] != -1:
			res.add(nums[right[i]] - nums[i])
	print(len(res))
t = int(_input())
for _ in range(t):
	n = int(_input())
	nums = singleLineArrInt()
	solve(n, nums)


import sys, threading
import math
from os import path
from collections import deque, defaultdict, Counter
from bisect import *
from string import ascii_lowercase
from functools import cmp_to_key
from random import randint
import heapq

def readInts():
	x = list(map(int, sys.stdin.readline().rstrip().split()))
	return x[0] if len(x) == 1 else x

def readList(type=int):
	x = sys.stdin.readline()
	x = list(map(type, x.rstrip('\n\r').split()))
	return x

def readStr():
	x = sys.stdin.readline().rstrip('\r\n')
	return x
write = sys.stdout.write
read = sys.stdin.readline
MAXN = 1123456

class mydict:

	def __init__(self, func=lambda : 0):
		self.random = randint(0, 1 << 32)
		self.default = func
		self.dict = {}

	def __getitem__(self, key):
		mykey = self.random ^ key
		if mykey not in self.dict:
			self.dict[mykey] = self.default()
		return self.dict[mykey]

	def get(self, key, default):
		mykey = self.random ^ key
		if mykey not in self.dict:
			return default
		return self.dict[mykey]

	def __setitem__(self, key, item):
		mykey = self.random ^ key
		self.dict[mykey] = item

	def getkeys(self):
		return [self.random ^ i for i in self.dict]

	def __str__(self):
		return f'{[(self.random ^ i, self.dict[i]) for i in self.dict]}'

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

def mod(n):
	return n % 1000000007

def solve(t):
	n = readInts()
	ar = readList()
	stack = []
	ans = set()
	for num in ar:
		while stack and stack[-1] < num:
			cur = stack.pop()
			ans.add(num - cur)
		if stack:
			ans.add(stack[-1] - num)
		stack.append(num)
	print(len(ans))

def main():
	t = 1
	if path.exists('/Users/arijitbhaumik/Library/Application Support/Sublime Text/Packages/User/input.txt'):
		sys.stdin = open('/Users/arijitbhaumik/Library/Application Support/Sublime Text/Packages/User/input.txt', 'r')
		sys.stdout = open('/Users/arijitbhaumik/Library/Application Support/Sublime Text/Packages/User/output.txt', 'w')
	t = readInts()
	for i in range(t):
		solve(i + 1)
main()


from bisect import bisect_left as lower_bound
from bisect import bisect_right as upper_bound

class FenwickTree:

	def __init__(self, x):
		bit = self.bit = list(x)
		size = self.size = len(bit)
		for i in range(size):
			j = i | i + 1
			if j < size:
				bit[j] += bit[i]

	def update(self, idx, x):
		while idx < self.size:
			self.bit[idx] += x
			idx |= idx + 1

	def __call__(self, end):
		x = 0
		while end:
			x += self.bit[end - 1]
			end &= end - 1
		return x

	def find_kth(self, k):
		idx = -1
		for d in reversed(range(self.size.bit_length())):
			right_idx = idx + (1 << d)
			if right_idx < self.size and self.bit[right_idx] <= k:
				idx = right_idx
				k -= self.bit[idx]
		return (idx + 1, k)

class SortedList:
	block_size = 700

	def __init__(self, iterable=()):
		self.macro = []
		self.micros = [[]]
		self.micro_size = [0]
		self.fenwick = FenwickTree([0])
		self.size = 0
		for item in iterable:
			self.insert(item)

	def insert(self, x):
		i = lower_bound(self.macro, x)
		j = upper_bound(self.micros[i], x)
		self.micros[i].insert(j, x)
		self.size += 1
		self.micro_size[i] += 1
		self.fenwick.update(i, 1)
		if len(self.micros[i]) >= self.block_size:
			self.micros[i:i + 1] = (self.micros[i][:self.block_size >> 1], self.micros[i][self.block_size >> 1:])
			self.micro_size[i:i + 1] = (self.block_size >> 1, self.block_size >> 1)
			self.fenwick = FenwickTree(self.micro_size)
			self.macro.insert(i, self.micros[i + 1][0])

	def pop(self, k=-1):
		(i, j) = self._find_kth(k)
		self.size -= 1
		self.micro_size[i] -= 1
		self.fenwick.update(i, -1)
		return self.micros[i].pop(j)

	def __getitem__(self, k):
		(i, j) = self._find_kth(k)
		return self.micros[i][j]

	def count(self, x):
		return self.upper_bound(x) - self.lower_bound(x)

	def __contains__(self, x):
		return self.count(x) > 0

	def lower_bound(self, x):
		i = lower_bound(self.macro, x)
		return self.fenwick(i) + lower_bound(self.micros[i], x)

	def upper_bound(self, x):
		i = upper_bound(self.macro, x)
		return self.fenwick(i) + upper_bound(self.micros[i], x)

	def _find_kth(self, k):
		return self.fenwick.find_kth(k + self.size if k < 0 else k)

	def __len__(self):
		return self.size

	def __iter__(self):
		return (x for micro in self.micros for x in micro)

	def __repr__(self):
		return str(list(self))
t = int(input())

def solve():
	N = int(input())
	A = [int(x) for x in input().split(' ')]
	sl = SortedList()
	indices = [[x, i] for (i, x) in enumerate(A)]
	indices.sort(reverse=True)
	ans = set()
	for (_, i) in indices:
		idx = sl.lower_bound(i)
		if idx > 0:
			ans.add(A[sl[idx - 1]] - A[i])
		if idx < len(sl):
			ans.add(A[sl[idx]] - A[i])
		sl.insert(i)
	print(len(ans))
while t:
	solve()
	t -= 1


from typing import List

def solving(arr: List[int], n: int) -> int:
	first1 = [0] * n
	second1 = [0] * n
	st = []
	s = set()
	first1[0] = -1
	st.append(arr[0])
	for i in range(1, n):
		while len(st) > 0 and arr[i] > st[-1]:
			st.pop()
		if len(st) == 0:
			first1[i] = -1
		else:
			first1[i] = st[-1]
		st.append(arr[i])
	while len(st) > 0:
		st.pop()
	second1[n - 1] = -1
	st.append(arr[n - 1])
	for i in range(n - 2, -1, -1):
		while len(st) > 0 and arr[i] >= st[-1]:
			st.pop()
		if len(st) != 0:
			second1[i] = st[-1]
		else:
			second1[i] = -1
		st.append(arr[i])
	for i in range(n):
		if first1[i] != -1:
			s.add(first1[i] - arr[i])
		if second1[i] != -1:
			s.add(second1[i] - arr[i])
	return len(s)

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


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	prev = [-1] * n
	next = [-1] * n
	stack = []
	for i in reversed(range(n)):
		while stack:
			if l[stack[-1]] < l[i]:
				stack.pop()
			else:
				break
		if stack:
			next[i] = stack[-1]
		stack.append(i)
	stack = []
	for i in range(n):
		while stack:
			if l[stack[-1]] < l[i]:
				stack.pop()
			else:
				break
		if stack:
			prev[i] = stack[-1]
		stack.append(i)
	ans = set()
	for i in range(n):
		if prev[i] != -1:
			ans.add(l[prev[i]] - l[i])
		if next[i] != -1:
			ans.add(l[next[i]] - l[i])
	print(len(ans))


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	stack = []
	prev_big = [-1] * n
	next_big = [-1] * n
	for i in range(n):
		while len(stack) > 0:
			if a[stack[-1]] < a[i]:
				stack.pop()
			else:
				break
		if len(stack) > 0:
			prev_big[i] = stack[-1]
		stack.append(i)
	stack = []
	for i in reversed(range(n)):
		while len(stack) > 0:
			if a[stack[-1]] < a[i]:
				stack.pop()
			else:
				break
		if len(stack) > 0:
			next_big[i] = stack[-1]
		stack.append(i)
	difs = set()
	for i in range(n):
		if prev_big[i] != -1:
			difs.add(a[prev_big[i]] - a[i])
		if next_big[i] != -1:
			difs.add(a[next_big[i]] - a[i])
	print(len(difs))


for t in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	(pref, suf) = ([None] * n, [None] * n)
	stack = []
	for i in range(n):
		while stack and stack[-1] < arr[i]:
			stack.pop()
		if stack:
			pref[i] = stack[-1]
		stack.append(arr[i])
	stack = []
	for i in range(n - 1, -1, -1):
		while stack and stack[-1] < arr[i]:
			stack.pop()
		if stack:
			suf[i] = stack[-1]
		stack.append(arr[i])
	ans = set()
	for i in range(n):
		if pref[i] != None:
			ans.add(pref[i] - arr[i])
		if suf[i] != None:
			ans.add(suf[i] - arr[i])
	print(len(ans))


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	res = set()
	st = []
	for i in range(n):
		while len(st) > 0 and st[len(st) - 1] <= l[i]:
			temp = l[i] - st[len(st) - 1]
			st.pop()
			res.add(temp)
		st.append(l[i])
	st = []
	for i in range(n - 1, -1, -1):
		while len(st) > 0 and st[len(st) - 1] <= l[i]:
			temp = l[i] - st[len(st) - 1]
			st.pop()
			res.add(temp)
		st.append(l[i])
	print(len(res))


from sys import stdin
input = stdin.readline

def previous_greatest_element(A):
	prev_greatest = [-1] * len(A)
	stack = []
	for i in range(len(A)):
		while stack:
			if A[i] > A[stack[-1]]:
				stack.pop()
			else:
				break
		if stack:
			prev_greatest[i] = stack[-1]
		stack.append(i)
	return prev_greatest

def next_greatest_element(A):
	next_greatest = [-1] * len(A)
	stack = []
	for i in reversed(range(len(A))):
		while stack:
			if A[i] > A[stack[-1]]:
				stack.pop()
			else:
				break
		if stack:
			next_greatest[i] = stack[-1]
		stack.append(i)
	return next_greatest

def solve(N, A):
	prev_greatest = previous_greatest_element(A)
	next_greatest = next_greatest_element(A)
	values = set()
	for i in range(N):
		if prev_greatest[i] != -1:
			values.add(A[prev_greatest[i]] - A[i])
		if next_greatest[i] != -1:
			values.add(A[next_greatest[i]] - A[i])
	return len(values)
T = int(input().strip())
for problem in range(1, T + 1):
	N = int(input().strip())
	A = [int(x) for x in input().strip().split()]
	print(solve(N, A))


for i in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	st = []
	r = set()
	for i in range(n):
		while len(st) > 0 and st[-1] <= arr[i]:
			temp = arr[i] - st[-1]
			st.pop()
			r.add(temp)
		st.append(arr[i])
	st = []
	for i in range(n - 1, -1, -1):
		while len(st) > 0 and st[-1] <= arr[i]:
			temp = arr[i] - st[-1]
			st.pop()
			r.add(temp)
		st.append(arr[i])
	print(len(r))


def solve(arr, n):
	s = []
	ans = set()
	for i in range(n - 1, -1, -1):
		if s and s[-1] > arr[i]:
			ans.add(s[-1] - arr[i])
		else:
			while s and s[-1] < arr[i]:
				s.pop()
			if s:
				ans.add(s[-1] - arr[i])
		s.append(arr[i])
	s = []
	for i in range(n):
		if s and s[-1] > arr[i]:
			ans.add(s[-1] - arr[i])
		else:
			while s and s[-1] < arr[i]:
				s.pop()
			if s:
				ans.add(s[-1] - arr[i])
		s.append(arr[i])
	return len(ans)
t = int(input())
while t:
	t -= 1
	n = int(input())
	a = list(map(int, input().split()))
	print(solve(a, n))


for _ in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split()]
	stack = [a[0]]
	base = a[0]
	se = set()
	for i in range(1, n):
		if a[i] >= stack[-1]:
			while stack[-1] <= a[i]:
				se.add(a[i] - stack[-1])
				stack.pop()
				if len(stack) == 0:
					break
		stack.append(a[i])
	stack = [a[-1]]
	base = a[-1]
	for i in range(n - 2, -1, -1):
		if a[i] >= stack[-1]:
			while a[i] >= stack[-1]:
				se.add(a[i] - stack[-1])
				stack.pop()
				if len(stack) == 0:
					break
		stack.append(a[i])
	print(len(se))


import heapq
for i in range(int(input())):
	s = set()
	n = int(input())
	l = list(map(int, input().split()))
	nex = [-1 for i in range(n)]
	prev = [-1 for i in range(n)]
	st = []
	for i in range(n):
		while st and l[st[-1]] <= l[i]:
			nex[st.pop()] = l[i]
		st.append(i)
	st = []
	for i in range(n - 1, -1, -1):
		while st and l[st[-1]] <= l[i]:
			prev[st.pop()] = l[i]
		st.append(i)
	for i in range(n):
		if nex[i] != -1:
			s.add(nex[i] - l[i])
		if prev[i] != -1:
			s.add(prev[i] - l[i])
	print(len(s))


import sys
from collections import deque

def main():
	tc = int(input())
	for _ in range(tc):
		n = int(input())
		arr = [int(a) for a in input().split()]
		nge_right = [-1 for i in range(n)]
		nge_left = [-1 for i in range(n)]
		stack = deque()
		for i in range(n - 1, -1, -1):
			while stack and stack[-1] < arr[i]:
				stack.pop()
			if stack:
				nge_right[i] = stack[-1]
			stack.append(arr[i])
		stack.clear()
		for i in range(n):
			while stack and stack[-1] < arr[i]:
				stack.pop()
			if stack:
				nge_left[i] = stack[-1]
			stack.append(arr[i])
		ans = set()
		for i in range(n):
			if nge_left[i] != -1:
				ans.add(nge_left[i] - arr[i])
			if nge_right[i] != -1:
				ans.add(nge_right[i] - arr[i])
		print(len(ans))
main()


for _ in range(int(input())):
	n = int(input())
	a = [int(i) for i in input().split()]
	(l, r) = ([0 for i in range(n)], [0 for i in range(n)])
	stk = []
	for i in range(n):
		while len(stk) and a[stk[-1]] <= a[i]:
			l[stk[-1]] = a[i]
			stk.pop()
		stk.append(i)
	stk = []
	for i in range(n - 1, -1, -1):
		while len(stk) and a[stk[-1]] <= a[i]:
			r[stk[-1]] = a[i]
			stk.pop()
		stk.append(i)
	ans = set()
	for i in range(n):
		if l[i]:
			ans.add(l[i] - a[i])
		if r[i]:
			ans.add(r[i] - a[i])
	print(len(ans))


t = int(input())
while t:
	t -= 1
	n = int(input())
	arr = [int(x) for x in input().split()]
	u = []
	left = [0] * n
	for i in range(n):
		while len(u) != 0 and u[-1] < arr[i]:
			u.pop()
		if len(u) == 0:
			left[i] = -1
		else:
			left[i] = u[-1]
		u.append(arr[i])
	mo = []
	right = [0] * n
	for i in range(n - 1, -1, -1):
		while len(mo) != 0 and mo[-1] < arr[i]:
			mo.pop()
		if len(mo) == 0:
			right[i] = -1
		else:
			right[i] = mo[-1]
		mo.append(arr[i])
	gi = set()
	ans = 0
	for i in range(n):
		g = left[i]
		h = right[i]
		if g != -1 and g - arr[i] not in gi:
			gi.add(g - arr[i])
			ans += 1
		if h != -1 and h - arr[i] not in gi:
			gi.add(h - arr[i])
			ans += 1
	print(ans)


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	b = []
	s = set()
	for i in range(n):
		while len(b) > 0 and b[-1] <= a[i]:
			val = a[i] - b[len(b) - 1]
			b.pop()
			s.add(val)
		b.append(a[i])
	b = []
	for i in range(n - 1, -1, -1):
		while len(b) > 0 and b[-1] <= a[i]:
			val = a[i] - b[len(b) - 1]
			b.pop()
			s.add(val)
		b.append(a[i])
	print(len(s))


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


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

def li():
	return list(mi())

def si():
	return str(input())

def lsi():
	return si().strip().split(' ')

def ni():
	return int(input())
for _ in range(ni()):
	n = ni()
	a = li()
	stack = []
	prev_big = [-1] * n
	next_big = [-1] * n
	for i in range(n):
		while len(stack) > 0:
			if a[stack[-1]] < a[i]:
				stack.pop()
			else:
				break
		if len(stack) > 0:
			prev_big[i] = stack[-1]
		stack.append(i)
	stack = []
	for i in reversed(range(n)):
		while len(stack) > 0:
			if a[stack[-1]] < a[i]:
				stack.pop()
			else:
				break
		if len(stack) > 0:
			next_big[i] = stack[-1]
		stack.append(i)
	difs = set()
	for i in range(n):
		if prev_big[i] != -1:
			difs.add(a[prev_big[i]] - a[i])
		if next_big[i] != -1:
			difs.add(a[next_big[i]] - a[i])
	print(len(difs))


t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	s = []
	left = [0] * n
	for i in range(n):
		while s and s[-1] < arr[i]:
			s.pop()
		if not s:
			left[i] = -1
		else:
			left[i] = s[-1]
		s.append(arr[i])
	s = []
	right = [0] * n
	for i in range(n - 1, -1, -1):
		while s and s[-1] < arr[i]:
			s.pop()
		if not s:
			right[i] = -1
		else:
			right[i] = s[-1]
		s.append(arr[i])
	sg = set()
	ans = 0
	for i in range(n):
		g = left[i]
		h = right[i]
		if g != -1 and g - arr[i] not in sg:
			sg.add(g - arr[i])
			ans += 1
		if h != -1 and h - arr[i] not in sg:
			sg.add(h - arr[i])
			ans += 1
	print(ans)


def countUnique(arr, n):
	ngl = [0 for i in range(n)]
	ngr = [0 for i in range(n)]
	st = []
	s = set()
	ngl[0] = -1
	st.append(arr[0])
	for i in range(1, n):
		while len(st) > 0 and arr[i] > st[-1]:
			st.pop()
		if len(st) == 0:
			ngl[i] = -1
		else:
			ngl[i] = st[-1]
		st.append(arr[i])
	while len(st) > 0:
		st.pop()
	ngr[n - 1] = -1
	st.append(arr[n - 1])
	for i in range(n - 2, -1, -1):
		while len(st) > 0 and arr[i] >= st[-1]:
			st.pop()
		if len(st) != 0:
			ngr[i] = st[-1]
		else:
			ngr[i] = -1
		st.append(arr[i])
	for i in range(n):
		if ngl[i] != -1:
			s.add(ngl[i] - arr[i])
		if ngr[i] != -1:
			s.add(ngr[i] - arr[i])
	return len(s)

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


for m1 in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	arr1 = list()
	arr2 = []
	minus = -1
	for i in range(n):
		arr1.append(0)
		arr2.append(0)
	s1 = list()
	s2 = set([])
	arr1[0] = minus
	s1.append(arr[0])
	start = 1
	for k in range(start, n):
		while len(s1) > 0 and arr[k] > s1[minus]:
			s1.pop()
		if len(s1) == 0:
			arr1[k] = minus
		else:
			arr1[k] = s1[minus]
		s23 = 5 + 67
		s23 += 3
		s1.append(arr[k])
	while len(s1) > 0:
		s1.pop()
		s234 = 5 + 67
		s234 += 3
	arr2[n - 1] = -1
	s1.append(arr[n - 1])
	r3 = 67
	r4 = 56
	r3 = r3 + r4
	for i in range(n - 2, -1, -1):
		while len(s1) > 0 and arr[i] >= s1[-1]:
			s1.pop()
		if len(s1) != 0:
			arr2[i] = s1[-1]
		else:
			arr2[i] = minus
		z = arr[i]
		s1.append(z)
	for i in range(n):
		s = 5 + 67
		s += 3
		if arr1[i] != -1:
			s2.add(arr1[i] - arr[i])
		if arr2[i] != -1:
			s2.add(arr2[i] - arr[i])
		s22 = 5 + 67
		s += 3
	count = 0
	count = len(s2)
	print(count)


t = int(input())
for i in range(0, t):
	n = int(input())
	a = list(map(int, input().split()))
	s1 = list()
	lmax = 0
	labmax = a[0]
	rmax = 0
	rabmax = a[n - 1]
	for x in range(1, n):
		if a[x] > labmax:
			labmax = a[x]
		elif a[x] > a[x - 1] and a[x] <= lmax:
			s1.append(lmax - a[x])
		else:
			for xx in range(x - 1, -1, -1):
				if a[x] <= a[xx]:
					s1.append(a[xx] - a[x])
					lmax = a[xx]
					break
	for x in range(n - 2, -1, -1):
		if a[x] > rabmax:
			rabmax = a[x]
		elif a[x] > a[x + 1] and a[x] <= rmax:
			s1.append(rmax - a[x])
		else:
			for xx in range(x + 1, n):
				if a[xx] >= a[x]:
					s1.append(a[xx] - a[x])
					rmax = a[xx]
					break
	print(len(set(s1)))


for j in range(int(input())):
	x = int(input())
	a = list(map(int, input().split()))
	supe = []
	lef = [0] * x
	for i in range(x):
		while supe and supe[-1] < a[i]:
			supe.pop()
		if not supe:
			lef[i] = -1
		else:
			lef[i] = supe[-1]
		supe.append(a[i])
	supe = []
	r = [0] * x
	for i in range(x - 1, -1, -1):
		while supe and supe[-1] < a[i]:
			supe.pop()
		if not supe:
			r[i] = -1
		else:
			r[i] = supe[-1]
		supe.append(a[i])
	shar = set()
	answer = 0
	for i in range(x):
		l = lef[i]
		right = r[i]
		if l != -1 and l - a[i] not in shar:
			shar.add(l - a[i])
			answer += 1
		if right != -1 and right - a[i] not in shar:
			shar.add(right - a[i])
			answer += 1
	print(answer)


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))[:n]
	l = [0] * n
	r = [0] * n
	stack = []
	temp = []
	l[0] = -1
	stack.append(a[0])
	for i in range(1, n):
		while len(stack) > 0 and a[i] > stack[len(stack) - 1]:
			stack.pop()
		if len(stack) == 0:
			l[i] = -1
		else:
			l[i] = stack[len(stack) - 1]
		stack.append(a[i])
	while len(stack) > 0:
		stack.pop()
	r[n - 1] = -1
	stack.append(a[n - 1])
	for i in range(n - 2, -1, -1):
		while len(stack) > 0 and a[i] > stack[len(stack) - 1]:
			stack.pop()
		if len(stack) != 0:
			r[i] = stack[len(stack) - 1]
		else:
			r[i] = -1
		stack.append(a[i])
	for i in range(n):
		if l[i] != -1:
			temp.append(l[i] - a[i])
		if r[i] != -1:
			temp.append(r[i] - a[i])
	temp = set(temp)
	print(len(temp))


def hmmmmm(n, arr):
	(a, b, c, s) = ([0] * n, [0] * n, [], set())
	a[0] = -1
	c.append(arr[0])
	for i in range(0, n - 1):
		while len(c) > 0 and arr[i + 1] > c[-1]:
			c.pop()
		if len(c) == 0:
			a[i + 1] = -1
		else:
			a[i + 1] = c[-1]
		c.append(arr[i + 1])
	while len(c) > 0:
		c.pop()
	b[n - 1] = -1
	c.append(arr[n - 1])
	for i in range(n - 3, -2, -1):
		while len(c) > 0 and arr[i + 1] >= c[-1]:
			c.pop()
		if len(c) != 0:
			b[i + 1] = c[-1]
		else:
			b[i + 1] = -1
		c.append(arr[i + 1])
	for i in range(n):
		if a[i] != -1:
			s.add(a[i] - arr[i])
		if b[i] != -1:
			s.add(b[i] - arr[i])
	return len(s)
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	print(hmmmmm(n, arr))


from collections import defaultdict
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	l1 = [l[0]]
	d = defaultdict(int)
	for i in range(1, n):
		while len(l1) and l[i] > l1[-1]:
			c = l1.pop()
			d[abs(l[i] - c)] += 1
		if len(l1):
			d[abs(l[i] - l1[-1])] += 1
		l1.append(l[i])
	ans = 0
	for i in d:
		ans += 1
	print(ans)


import sys, os
from io import BytesIO, IOBase
mod = 10 ** 9 + 7
Mod = 998244353
INF = float('inf')
input = lambda : sys.stdin.readline().rstrip('\r\n')
inp = lambda : list(map(int, sys.stdin.readline().rstrip('\r\n').split()))
tc = 1
tc = int(input())
for test_cases in range(1, tc + 1):
	(n,) = inp()
	a = inp()
	ans = set()

	def nge():
		stack = []
		for i in a:
			while stack and stack[-1] <= i:
				ans.add(i - stack.pop())
			stack.append(i)
	nge()
	a.reverse()
	nge()
	print(len(ans))


def nge(arr):
	n = len(arr)
	nge = [-1] * n
	stack = [arr[-1]]
	s = 1
	i = -2
	while i >= -n:
		if s > 0:
			curr = arr[i]
			while s > 0 and curr > stack[-1]:
				stack.pop()
				s -= 1
			if s > 0:
				nge[i] = stack[-1]
		stack.append(arr[i])
		s += 1
		i -= 1
	return nge

def main():
	n = int(input())
	arr = list(map(int, input().split()))
	ng1 = nge(arr)
	arr = arr[::-1]
	ng2 = nge(arr)
	ng2 = ng2[::-1]
	arr = arr[::-1]
	st = set()
	for i in range(n):
		if ng1[i] != -1:
			st.add(ng1[i] - arr[i])
		if ng2[i] != -1:
			st.add(ng2[i] - arr[i])
	return len(st)
for _ in range(int(input())):
	print(main())


from itertools import *

def check(arr, start, end):
	n = len(arr)
	if arr[0] == start and arr[1] == end:
		for i in range(1, n - 1):
			if arr[i] % (i + 1) != 0:
				return 0
		return 1
	else:
		return 0

def func(n, start):
	lst = []
	for i in range(1, n + 1):
		lst.append(i)
	perm = permutations(lst)
	end = 1
	for i in perm:
		if check(i, start, end) == 1:
			print(i)

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
testcases = int(input())
for i in range(testcases):
	n = int(input())
	arr = [int(x) for x in input().split()]
	answer = pairs(arr)
	count = 0
	dic = {}
	for i in answer:
		diff = abs(i[0] - i[1])
		if diff in dic:
			dic[diff] += 1
		else:
			dic[diff] = 1
			count += 1
	print(count)


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
t = int(input())
mod = 1000000007
for i in range(t):
	n = int(input())
	arr = [int(x) for x in input().split()]
	pair = pairs(arr)
	s = set()
	for i in pair:
		s.add(abs(i[0] - i[1]))
	print(len(s))