An array A is called *weird* if it can be sorted in non-decreasing order by applying the given operation any number of times:
Select any index i (1 ≤ i ≤ |A|) and set A_{i} := -A_{i}.

For example: A = [2, 1, 3] is *weird* since after applying the operation at i = 1, A becomes [-2, 1, 3] which is sorted.

JJ has a permutation P of length N. He wants to find the number of subarrays of P which are *weird*. Can you help him?

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

- The first line contains a single integer T — the number of test cases. Then the test cases follow.
- The first line of each test case contains an integer N — the size of the permutation P.
- The second line of each test case contains N space-separated integers P_{1}, P_{2}, \dots, P_{N} denoting the permutation P.

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

For each test case, output on a new line the number of *weird* subarrays of P.

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

$1 ≤ T ≤ 10^{5}$
$1 ≤ N ≤ 10^{5}$
$P$ is a permutation.
- Sum of $N$ over all test cases does not exceed $2 \cdot 10^{5}$.

----- Sample Input 1 ------ 
3
3
2 3 1
3
2 1 3
4
1 2 3 4

----- Sample Output 1 ------ 
5
6
10

----- explanation 1 ------ 
Test Case 1: Weird subarrays of $P$ are: $[2], [3], [1], [2, 3], [3, 1]$.

Test Case 2: Weird subarrays of $P$ are: $[2], [1], [3], [2, 1], [1, 3], [2, 1, 3]$.

Source: codechef | Difficulty: MEDIUM_HARD
Tags: Dynamic programming


Solutions:
for _ in range(int(input())):
	N = int(input())
	A = list(map(int, input().split()))
	if N == 1:
		print(1)
	elif N == 2:
		print(3)
	else:
		C = 2
		F = A[1] > A[0]
		final = 0
		for i in range(2, N):
			if not F or (F and A[i] > A[i - 1]):
				if not F and A[i] > A[i - 1]:
					F = True
				C += 1
			else:
				final += C * (C + 1) // 2
				if final > C * (C + 1) // 2:
					final -= 1
				C = 2
				F ^= True
		if C > 0:
			final += C * (C + 1) // 2
			if final > C * (C + 1) // 2:
				final -= 1
		print(final)


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	(dpl, dpr) = ([1] * n, [1] * n)
	for i in range(1, n):
		if arr[i - 1] > arr[i]:
			dpl[i] += dpl[i - 1]
	for i in range(n - 1, 0, -1):
		if arr[i] > arr[i - 1]:
			dpr[i - 1] += dpr[i]
	ans = 0
	for i in range(n):
		ans += dpl[i] * dpr[i]
	print(ans)


for t in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	(dpl, dpr) = ([1] * n, [1] * n)
	for i in range(1, n):
		if a[i] < a[i - 1]:
			dpl[i] += dpl[i - 1]
	for i in range(n - 1, 0, -1):
		if a[i - 1] < a[i]:
			dpr[i - 1] += dpr[i]
	ans = 0
	for i in range(n):
		ans += dpl[i] * dpr[i]
	print(ans)


for _ in range(int(input())):
	n = int(input())
	lis = list(map(int, input().split()))
	ans = 1
	i = 0
	j = 1
	las = None
	while j < n:
		if las == None:
			if lis[j] > lis[j - 1]:
				las = 'inc'
				ans += 2
			else:
				las = 'dec'
				ans += 2
		elif las == 'inc':
			if lis[j] >= lis[j - 1]:
				ans += j - i + 1
			else:
				las = 'dec'
				i = j - 1
				ans += 2
		elif lis[j] >= lis[j - 1]:
			las = 'inc'
			ans += j - i + 1
		else:
			ans += j - i + 1
		j += 1
	print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	ans = 0
	inc = [0] * n
	desc = [0] * n
	inc[n - 1] = desc[n - 1] = 1
	for i in reversed(range(n - 1)):
		if a[i] < a[i + 1]:
			inc[i] = inc[i + 1] + 1
		else:
			inc[i] = 1
		if a[i] > a[i + 1]:
			desc[i] = desc[i + 1] + 1
		else:
			desc[i] = 1
	for i in range(n):
		if inc[i] > 1:
			ans = ans + inc[i]
		elif desc[i] > 1:
			ans = ans + desc[i]
			j = i + desc[i]
			if j < n:
				ans = ans + inc[j]
		else:
			ans = ans + 1
	print(ans)


def perms3orbigger(x):
	return x * (x + 1) // 2 - (x + x) + 1

def isWeird3v2(l, h):
	return p[l] > p[l + 1] or p[l + 1] < p[l + 2]

def extendsv2(l, h):
	return p[h - 2] < p[h - 1] or p[h - 3] > p[h - 2]

def pretendsv2(l, h):
	return p[l + 1] < p[l + 2] or p[l] > p[l + 1]

def countWeirds(lo, hi):
	if lo + 3 > hi:
		return 0
	if lo + 3 == hi:
		return int(isWeird3v2(lo, hi))
	tophit = bothit = False
	if isWeird3v2((midlo := ((lo + hi - 1) // 2 - 1)), (midhi := (midlo + 3))):
		while (midhi == hi or extendsv2(midlo, (midhi := (midhi + 1)))) and (midlo == lo or pretendsv2((midlo := (midlo - 1)), midhi)):
			if (tophit := (midhi == hi)) and (bothit := (midlo == lo)):
				return perms3orbigger(hi - lo)
	return -perms3orbigger(midhi - midlo - 2) + (perms3orbigger(midhi - lo - 1) if bothit else countWeirds(lo, midhi - 1)) + (perms3orbigger(hi - midlo - 1) if tophit else countWeirds(midlo + 1, hi))
for _ in range(int(input())):
	n = int(input())
	p = list(map(int, input().split()))
	ans = n + n - 1
	if n > 2:
		ans += countWeirds(0, n)
	print(ans)


def sum(n):
	if n > 2:
		return (n - 2) * (n - 1) / 2
	return 0
a = int(input())
for i in range(a):
	b = int(input())
	array = list(map(int, input().split()))
	count = b + b - 1
	ini = 0
	f = 1
	while f < len(array) - 1:
		if array[f + 1] < array[f] > array[f - 1]:
			count += sum(f - ini + 1)
			ini = f
		elif f == len(array) - 1:
			count += sum(f + 1 - ini + 1)
		f += 1
	count += sum(f - ini + 1)
	print(int(count))


for _ in range(int(input())):
	n = int(input())
	p = list(map(int, input().split()))
	ans = 0
	p[0] *= -1
	count = 1
	flag = 0
	for i in range(1, n):
		if -p[i] > p[i - 1]:
			count += 1
			p[i] *= -1
		elif p[i] > p[i - 1]:
			count += 1
		else:
			p[i - 1] *= -1
			if -p[i] > p[i - 1]:
				p[i] *= -1
			count = (count + 1) * count // 2
			if flag != 0:
				count -= 1
			flag += 1
			ans += count
			count = 2
	count = (count + 1) * count // 2
	if flag != 0:
		count -= 1
	ans += count
	print(ans)


def calculate(arr, n):
	inc = [1 for i in range(n)]
	dec = [1 for i in range(n)]
	for i in range(n - 2, -1, -1):
		if arr[i] < arr[i + 1]:
			inc[i] = inc[i + 1] + 1
		else:
			dec[i] = dec[i + 1] + 1
	count = 1
	for i in range(n):
		if inc[i] > 1:
			count += inc[i]
		elif dec[i] > 1:
			count += dec[i]
			if i + dec[i] < n:
				count += inc[i + dec[i]]
	return count
T = int(input())
ans = []
for i in range(T):
	n = int(input())
	arr = list(map(int, input().split()))
	v = calculate(arr, n)
	ans.append(v)
for i in ans:
	print(i)


t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	ans = 0
	c = 0
	prev = 1
	curr = 1
	for i in range(n - 1):
		if arr[i] <= arr[i + 1]:
			prev = curr
			curr = 1
			c += 1
		else:
			prev = curr
			curr = 0
			if prev == 1 and curr == 0:
				ans += (c + 1) * c // 2
				c = 0
			c += 1
	ans += (c + 1) * c // 2 + n
	print(ans)


T = int(input())
for _ in range(T):
	N = int(input())
	P = list(map(int, input().split()))
	if N == 1:
		print(1)
	else:
		peaks = []
		if P[0] > P[1]:
			peaks.append(0)
		for i in range(1, N - 1):
			if P[i - 1] < P[i] and P[i + 1] < P[i]:
				peaks.append(i)
		if P[N - 1] > P[N - 2]:
			peaks.append(N - 1)
		peak_gaps = [peaks[0] - 0]
		for i in range(1, len(peaks)):
			peak_gaps.append(peaks[i] - peaks[i - 1])
		peak_gaps.append(N - 1 - peaks[-1])
		count = N
		for i in peak_gaps:
			count += i * (i + 1) // 2
		print(count)


for i in range(int(input())):
	n = int(input())
	array = list(map(int, input().split()))
	k = 1
	ans = 1
	array[0] = min(-array[0], array[0])
	for j in range(n - 1):
		if max(array[j + 1], -array[j + 1]) > array[j]:
			k += 1
			if -array[j + 1] > array[j]:
				array[j + 1] = -array[j + 1]
		else:
			ans += k * (k + 1) // 2 - 1
			k = 2
			if -array[j + 1] > -abs(array[j]):
				array[j + 1] = -array[j + 1]
	ans += k * (k + 1) // 2 - 1
	print(ans)


T = int(input())
for i in range(T):
	n = int(input())
	p = list(map(int, input().split()))
	k = 1
	ans = 1
	p[0] = -p[0]
	for j in range(n - 1):
		if p[j + 1] > p[j]:
			k += 1
			if -p[j + 1] > p[j]:
				p[j + 1] = -p[j + 1]
		else:
			ans += k * (k + 1) // 2 - 1
			k = 2
			if -p[j + 1] > -abs(p[j]):
				p[j + 1] = -p[j + 1]
	ans += k * (k + 1) // 2 - 1
	print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	in1 = [1]
	dc1 = [1]
	j = 0
	for i in range(n - 2, -1, -1):
		if l[i] < l[i + 1]:
			in1.append(in1[j] + 1)
		else:
			in1.append(1)
		j += 1
	j = 0
	for i in range(n - 2, -1, -1):
		if l[i] > l[i + 1]:
			dc1.append(dc1[j] + 1)
		else:
			dc1.append(1)
		j += 1
	in1 = in1[::-1]
	dc1 = dc1[::-1]
	ans = 0
	for i in range(n):
		if in1[i] > 1:
			ans += in1[i]
		elif dc1[i] > 1:
			ans += dc1[i]
			j = i + dc1[i]
			if j < n:
				ans += in1[j]
		else:
			ans += 1
	print(ans)


numInp = lambda : int(input())
lstImp = lambda : list(map(int, input().split()))
strImp = lambda : input()
spacedStrImp = lambda : list(input())
seperateImp = lambda : map(int, input().split())
for i in range(int(input())):
	lenOfPermutation = numInp()
	permutation = lstImp()
	ans = 0
	check = 0
	previous = 1
	current = 1
	for i in range(lenOfPermutation - 1):
		previous = current
		if permutation[i] <= permutation[i + 1]:
			current = 1
		else:
			current = 0
			if previous == 1 and (not current):
				ans += (check + 1) * check // 2
				check = 0
		check += 1
	ans += (check + 1) * check // 2 + lenOfPermutation
	print(ans)


t = int(input())
for i in range(t):
	n = int(input())
	a = [int(x) for x in input().split()]
	inc = [1] * n
	dec = [1] * n
	for i in range(n - 2, -1, -1):
		if a[i] > a[i + 1]:
			dec[i] = dec[i + 1] + 1
		else:
			dec[i] = 1
		if a[i] < a[i + 1]:
			inc[i] = inc[i + 1] + 1
		else:
			inc[i] = 1
	a = 0
	for i in range(n):
		if inc[i] > 1:
			a = a + inc[i]
		elif dec[i] > 1:
			a = a + dec[i]
			j = i + dec[i]
			if j < n:
				a = a + inc[j]
		elif inc[i] == 1 and inc[i] == 1:
			a = a + 1
	print(a)


import os, sys, io, math
from array import array
from math import *
from collections import Counter
I = lambda : [*map(int, sys.stdin.readline().split())]
IS = lambda : input()
IN = lambda : int(input())
IF = lambda : float(input())
for _ in range(IN()):
	(n, l, a, c, ok) = (IN(), I(), 1, 1, False)
	for i in range(1, n):
		if l[i] > l[i - 1]:
			c += 1
			a += c
			ok = True
		elif ok:
			c = 2
			a += c
			ok = False
		else:
			c += 1
			a += c
	print(a)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	wl = n
	a = l
	op = 1
	i = 0
	for j in range(i + 1, n):
		if a[j - 1] < a[j]:
			wl += j - i
			op = 0
		elif -1 * a[j - 1] < a[j] and op == 1:
			a[j - 1] = a[j - 1] * -1
			wl += j - i
			if a[j - 1] > a[j] * -1:
				op = 0
		elif -1 * a[j - 1] < a[j]:
			op = 1
			i = j - 1
			a[j - 1] = a[j - 1] * -1
			wl += j - i
			if a[j - 1] > a[j] * -1:
				op = 0
		else:
			i = j
			op = 1
	print(wl)


for _ in range(int(input())):
	N = int(input())
	numbers = input().split()
	for i in range(N):
		numbers[i] = int(numbers[i])
	counter = 0
	initial = 1
	count = 0
	for i in range(N):
		try:
			if numbers[i] > numbers[i - 1] and numbers[i] > numbers[i + 1]:
				counter += 1
				order = i + 1
				total = order - initial + 1
				count += int(total * (total + 1) / 2)
				initial = order
		except IndexError:
			pass
	if counter == 0:
		print(int(N * (N + 1) / 2))
	else:
		total = N - initial + 1
		count += int(total * (total + 1) / 2)
		count -= counter
		print(count)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	i = 0
	ans = n
	while i < n:
		j = i
		while j + 1 < n:
			if a[j] > a[j + 1]:
				if j - 1 >= i and a[j - 1] > -a[j]:
					break
				a[j] = -a[j]
			j += 1
		k = j - i + 1
		ans += k * (k + 1) // 2 - k
		i = max(i + 1, j)
	print(ans)


for _ in range(int(input())):
	n = int(input())
	p = list(map(int, input().split()))
	(left, right) = ([1] * n, [1] * n)
	for i in range(1, n):
		if p[i] < p[i - 1]:
			left[i] += left[i - 1]
		if p[n - 1 - i] < p[n - i]:
			right[n - 1 - i] += right[n - i]
	print(sum((left[i] * right[i] for i in range(n))))


s = int(input())
for i in range(0, s):
	x = input()
	n = list(map(int, input().split()))
	dp = [[1, 1] for k in range(0, len(n))]
	for k in range(1, len(n)):
		if n[k] > n[k - 1]:
			dp[k][0] = dp[k - 1][0] + 1
		else:
			dp[k][1] = dp[k - 1][1] + 1
			dp[k][0] = dp[k][1]
	c1 = 0
	for i in range(0, len(n)):
		x1 = max(dp[i])
		c1 = c1 + x1
	print(c1)


T = int(input())
for _ in range(T):
	n = int(input())
	arr = list(map(int, input().split()))
	left = [1] * n
	dec = [1] * n
	for i in range(len(arr) - 2, -1, -1):
		if arr[i] <= arr[i + 1]:
			left[i] = left[i + 1] + 1
		if arr[i] >= arr[i + 1]:
			dec[i] = dec[i + 1] + 1
	ans = 0
	for i in range(n):
		if left[i] > 1:
			ans += left[i]
		elif dec[i] > 1:
			ans += dec[i]
			if i + dec[i] < n:
				ans += left[i + dec[i]]
		else:
			ans += 1
	print(ans)


for _ in range(int(input())):
	n = int(input())
	p = list(map(int, input().split()))
	hills = []
	for i in range(1, n - 1):
		if p[i - 1] < p[i] and p[i] > p[i + 1]:
			hills.append(i)
	hills.append(n - 1)
	length = []
	prev = 0
	for hill in hills:
		length.append(hill - prev + 1)
		prev = hill
	ans = 0
	for num in length:
		ans += num * (num + 1) // 2
	print(ans - len(hills) + 1)


for t in range(int(input())):
	N = int(input())
	P = list(map(int, input().split()))
	(hill, h) = ([], [])
	C = 0
	for i in range(1, N - 1):
		if P[i - 1] < P[i] and P[i] > P[i + 1]:
			hill.append(i)
	h.append(0)
	h.extend(hill)
	h.append(N - 1)
	for i in range(len(h) - 1):
		B = h[i + 1] - h[i] + 1
		C += B * (B + 1) // 2
	C -= len(hill)
	print(C)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	hills = []
	for i in range(1, n - 1):
		if l[i - 1] < l[i] and l[i] > l[i + 1]:
			hills.append(i)
	hills = [0] + hills + [n - 1]
	count = 0
	for i in range(1, len(hills)):
		length = hills[i] - hills[i - 1] + 1
		count += length * (length + 1) // 2
	count += 2 - len(hills)
	print(count)


for _ in range(int(input())):
	n = int(input())
	L = list(map(int, input().split(' ')))
	inc = [1] * n
	dec = [1] * n
	for i in range(n - 2, -1, -1):
		if L[i] > L[i + 1]:
			dec[i] = dec[i + 1] + 1
		else:
			inc[i] = inc[i + 1] + 1
	res = 0
	for i in range(n):
		if inc[i] > 1:
			res += inc[i]
		elif dec[i] > 1:
			res += dec[i]
			j = i + dec[i]
			if j < n:
				res += inc[j]
		else:
			res += 1
	print(res)


t = int(input())
for _ in range(t):
	N = int(input())
	P = list(map(int, input().split()))
	left = [1] * N
	right = [1] * N
	for i in range(1, N):
		if P[i] < P[i - 1]:
			left[i] += left[i - 1]
		if P[N - (1 + i)] < P[N - i]:
			right[N - (1 + i)] += right[N - i]
	count = 0
	for i in range(N):
		count += left[i] * right[i]
	print(count)


for trie in range(int(input())):
	N = int(input())
	LST = list(map(int, input().split()))
	arr = [0]
	for i in range(1, N - 1):
		if LST[i - 1] < LST[i] > LST[i + 1]:
			arr.append(i)
	ANSWER = N
	arr.append(N - 1)
	for i in range(len(arr) - 1):
		x = arr[i + 1] - arr[i]
		ANSWER += (x + 1) * x // 2
	print(ANSWER)


t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	(inc, dec) = ([0] * n, [0] * n)
	inc[n - 1] = dec[n - 1] = 1
	for i in range(n - 2, -1, -1):
		if arr[i + 1] > arr[i]:
			inc[i] = inc[i + 1] + 1
		else:
			inc[i] = 1
		if arr[i + 1] < arr[i]:
			dec[i] = dec[i + 1] + 1
		else:
			dec[i] = 1
	ans = 0
	for i in range(n):
		if inc[i] > 1:
			ans += inc[i]
		elif dec[i] > 1:
			ans += dec[i]
			j = i + dec[i]
			if j < n:
				ans += inc[j]
		else:
			ans += 1
	print(ans)


for _ in range(int(input())):
	n = int(input())
	p = list(map(int, input().split()))
	incr = [1 for _ in range(n)]
	decr = [1 for _ in range(n)]
	for i in range(1, n):
		if p[i] < p[i - 1]:
			decr[i] += decr[i - 1]
		if p[n - 1 - i] < p[n - i]:
			incr[n - 1 - i] += incr[n - i]
	summ = 0
	for i in range(n):
		summ += incr[i] * decr[i]
	print(summ)


t = int(input())
for _ in range(t):
	n = int(input())
	A = [int(x) for x in input().split()]
	inc = [0] * n
	dec = [0] * n
	inc[n - 1] = dec[n - 1] = 1
	ans = 0
	for i in range(n - 1):
		j = n - 2 - i
		if A[j] > A[j + 1]:
			dec[j] = dec[j + 1] + 1
			inc[j] = 1
		else:
			inc[j] = inc[j + 1] + 1
			dec[j] = 1
	for i in range(n):
		if inc[i] > 1:
			ans += inc[i]
		elif dec[i] > 1:
			ans += dec[i]
			k = i + dec[i]
			if k < n:
				ans += inc[k]
		else:
			ans += 1
	print(ans)


def weirdArr(n, p):
	left = [1] * n
	right = [1] * n
	for i in range(1, n):
		if p[i] < p[i - 1]:
			left[i] += left[i - 1]
		if p[n - i - 1] < p[n - i]:
			right[n - i - 1] += right[n - i]
	ans = 0
	for i in range(n):
		ans += left[i] * right[i]
	return ans
t = int(input())
for _ in range(t):
	n = int(input())
	p = [int(x) for x in input().split()]
	ans = weirdArr(n, p)
	print(ans)


from itertools import islice
import sys
for s in islice(sys.stdin, 2, None, 2):
	a = [*map(int, s.split())]
	m = 0
	r = len(a) * 2 - 1
	for (x, y, z) in zip(a, a[1:], a[2:]):
		if x < y > z:
			m = 0
		else:
			m += 1
			r += m
	print(r)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	arr = [0]
	for i in range(1, n - 1):
		if l[i - 1] < l[i] > l[i + 1]:
			arr.append(i)
	ans = n
	arr.append(n - 1)
	for i in range(len(arr) - 1):
		x = arr[i + 1] - arr[i]
		ans += (x + 1) * x // 2
	print(ans)


def solve(n, arr):
	res = 0
	decreasing = [0] * n
	increasing = [0] * n
	for i in range(1, n):
		decreasing[i] = i if arr[i] < arr[i - 1] else decreasing[i - 1]
		increasing[i] = i if arr[i] > arr[i - 1] else increasing[i - 1]
	for i in range(n):
		res += i - decreasing[i] + 1
		res += i - increasing[i]
		if increasing[decreasing[i]] < increasing[i]:
			res += decreasing[i] - increasing[decreasing[i]]
	return res
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	print(solve(n, arr))


import sys
from itertools import islice
for s in islice(sys.stdin, 2, None, 2):
	a = (*map(int, s.split()),)
	n = len(a)
	r = 2 * n - 1
	m = 0
	for i in range(n - 2):
		if a[i] < a[i + 1] > a[i + 2]:
			m = 0
		else:
			m += 1
			r += m
	print(r)


import sys
from itertools import islice
for s in islice(sys.stdin, 2, None, 2):
	a = (*map(int, s.split()),)
	s = ''.join(('* '[x < y > z] for (x, y, z) in zip(a, a[1:], a[2:])))
	print(2 * len(a) - 1 + sum((l * (l + 1) // 2 for l in map(len, s.split()))))


def solve(aa, nn):
	ff = [1] * nn
	gg = [1] * nn
	for i in range(1, nn):
		if aa[i] > aa[i - 1]:
			ff[i] += ff[i - 1]
		if aa[i] < aa[i - 1]:
			ff[i] += gg[i - 1]
			gg[i] += gg[i - 1]
	ans = 0
	for i in range(nn):
		ans += max(ff[i], gg[i])
	return ans
tt = int(input())
for _ in range(tt):
	nn = int(input())
	aa = list(map(int, input().split()))
	print(solve(aa, nn))


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	s = 0
	ans = n + 0
	f = 0
	for i in range(1, n):
		if f == 2:
			if a[i] < a[i - 1]:
				f = i - s
				ans += f * (f + 1) // 2 - f
				s = i - 1
				f = 1
		elif f == 1:
			if a[i] > a[i - 1]:
				f = 2
		elif a[i] > a[i - 1]:
			f = 2
		elif a[i] < a[i - 1]:
			f = 1
	if s < n - 1:
		f = n - s
		ans += f * (f + 1) // 2 - f
		s = i
	print(ans)


for _ in range(int(input())):
	n = int(input())
	p = list(map(int, input().split()))
	l = [1] * n
	r = [1] * n
	for i in range(1, n):
		if p[i] <= p[i - 1]:
			l[i] += l[i - 1]
	for i in range(n - 2, -1, -1):
		if p[i] < p[i + 1]:
			r[i] += r[i + 1]
	ans = 0
	for i in range(n):
		ans += l[i] * r[i]
	print(ans)


t = int(input())
for _ in range(t):
	tot = 0
	n = int(input())
	(l, r) = ([1] * n, [1] * n)
	arr = list(map(int, input().split()))
	for i in range(1, n):
		if arr[i] < arr[i - 1]:
			l[i] += l[i - 1]
		if arr[n - i - 1] < arr[n - i]:
			r[n - i - 1] += r[n - i]
	print(sum((l[i] * r[i] for i in range(n))))


def solve(a, n):
	f = [1] * n
	g = [1] * n
	for i in range(1, n):
		if a[i] > a[i - 1]:
			f[i] += f[i - 1]
		if a[i] < a[i - 1]:
			f[i] += g[i - 1]
			g[i] += g[i - 1]
	ans = 0
	for i in range(n):
		ans += max(f[i], g[i])
	return ans
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	print(solve(a, n))


for _ in range(int(input())):
	n = int(input())
	p = list(map(int, input().split()))
	a = [0]
	ans = n
	for i in range(1, n - 1):
		if p[i] > p[i - 1] and p[i] > p[i + 1]:
			a.append(i)
	a.append(n - 1)
	for i in range(1, len(a)):
		l = a[i] - a[i - 1] + 1
		ans += l * (l - 1) // 2
	print(ans)


def weirdArr(n, p):
	hills = [0]
	for i in range(1, n - 1):
		if p[i] > p[i - 1] and p[i] > p[i + 1]:
			hills.append(i)
	hills.append(n - 1)
	ans = 0
	for i in range(0, len(hills) - 1):
		leng = hills[i + 1] - hills[i] + 1
		ans += leng * (leng - 1) // 2
	ans += n
	return ans
t = int(input())
for _ in range(t):
	n = int(input())
	p = [int(x) for x in input().split()]
	ans = weirdArr(n, p)
	print(ans)


for _ in range(int(input())):
	n = int(input())
	x = 0
	a = list(map(int, input().split()))
	(pref, suff) = ([1] * n, [1] * n)
	for i in range(1, n):
		if a[i] < a[i - 1]:
			pref[i] += pref[i - 1]
		if a[n - i - 1] < a[n - i]:
			suff[n - i - 1] += suff[n - i]
	ans = 0
	for i in range(n):
		ans += pref[i] * suff[i]
	print(ans)


t = int(input())
for i in range(t):
	n = int(input())
	p = list(map(int, input().split()))
	dec = [0] * n
	inc = [0] * n
	dec[n - 1] = n - 1
	inc[n - 1] = n - 1
	i = n - 2
	while i >= 0:
		if p[i] > p[i + 1]:
			dec[i] = dec[i + 1]
			inc[i] = i
		else:
			dec[i] = i
			inc[i] = inc[i + 1]
		i -= 1
	sm = 0
	for i in range(n):
		j = dec[i]
		k = inc[j]
		sm += k - i + 1
	print(sm)


for _ in range(int(input())):
	n = int(input())
	p = list(map(int, input().split()))
	count = 1
	up = False
	ans = 0
	for i in range(1, n):
		if p[i] > p[i - 1]:
			count += 1
			up = True
		elif up:
			ans += (count - 1) * count // 2
			up = False
			count = 2
		else:
			count += 1
	ans += (count - 1) * count // 2 + n
	print(ans)


for messi in range(int(input())):
	n = int(input())
	p = list(map(int, input().split(' ')))
	hill = []
	ans = 0
	hill.append(0)
	for i in range(1, n - 1):
		if p[i] > p[i - 1] and p[i] > p[i + 1]:
			hill.append(i)
	hill.append(n - 1)
	for i in range(len(hill) - 1):
		dist = hill[i + 1] - hill[i] + 1
		ans += dist * (dist - 1) // 2
	ans += n
	print(ans)


for _ in range(int(input())):
	n = int(input())
	p = list(map(int, input().split()))
	v = []
	v.append(1)
	for i in range(1, n - 1):
		if p[i] > p[i - 1] and p[i] > p[i + 1]:
			v.append(i + 1)
	v.append(n)
	ans = 0
	c = 0
	for i in range(1, len(v)):
		c = v[i] - v[i - 1] + 1
		ans += c * (c + 1) // 2
	ans -= len(v) - 2
	print(ans)


for T in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	dec = [0] * n
	inc = [0] * n
	dec[n - 1] = n - 1
	inc[n - 1] = n - 1
	for i in range(n - 2, -1, -1):
		if l[i] > l[i + 1]:
			dec[i] = dec[i + 1]
			inc[i] = i
		else:
			inc[i] = inc[i + 1]
			dec[i] = i
	ans = 0
	for i in range(n):
		j = dec[i]
		k = inc[j]
		ans += k - i + 1
	print(ans)


from sys import stdin
input = stdin.readline

def solve(N, P):
	count = 0
	hills = [i for i in range(1, N - 1) if P[i - 1] < P[i] > P[i + 1]]
	hills = [0] + hills + [N - 1]
	for (left, right) in zip(hills, hills[1:]):
		size = right - left + 1
		count += size * (size - 1) // 2
	return count + N
T = int(input().strip())
for problem in range(1, T + 1):
	N = int(input().strip())
	P = [int(x) for x in input().strip().split()]
	print(solve(N, P))


for _ in range(int(input())):
	n = int(input())
	p = list(map(int, input().strip().split()))
	res = 0
	l = [0]
	for i in range(1, n - 1):
		if p[i - 1] < p[i] > p[i + 1]:
			l.append(i)
	l.append(n - 1)
	for i in range(len(l) - 1):
		temp = l[i + 1] - l[i] + 1
		res += temp * (temp - 1) / 2
	res += n
	print(int(res))


import bisect
import math
import sys
from collections import Counter, deque
for _ in range(int(sys.stdin.readline())):
	n = int(sys.stdin.readline())
	a = [int(i) for i in sys.stdin.readline().split()]
	ans = 0
	l = [0]
	for i in range(1, len(a) - 1):
		if a[i - 1] < a[i] > a[i + 1]:
			l.append(i)
	l.append(n - 1)
	for i in range(0, len(l) - 1):
		temp = l[i + 1] - l[i] + 1
		ans += temp * (temp - 1) / 2
	ans += n
	print(int(ans))


def soln(n, arr):
	streak = 1
	res = 0
	i = 0
	while i < n - 1:
		if arr[i] < arr[i + 1]:
			i += 1
			streak += 1
		else:
			arr[i] = -arr[i]
			if i > 0 and arr[i - 1] > 0:
				if res != 0:
					res -= 1
				res += streak * (streak + 1) // 2
				streak = 1
	if res != 0:
		res -= 1
	res += streak * (streak + 1) // 2
	return res
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	print(soln(n, arr))


def soln(n, arr):
	left = [1]
	for i in range(1, n):
		if arr[i - 1] > arr[i]:
			left.append(left[-1] + 1)
		else:
			left.append(1)
	right = [1] * n
	for i in range(n - 2, -1, -1):
		if arr[i + 1] > arr[i]:
			right[i] = 1 + right[i + 1]
	res = 0
	for i in range(n):
		res += left[i] * right[i]
	return res
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	print(soln(n, arr))


ans = []
nq = int(input())
for _ in range(nq):
	n = int(input())
	A = list(map(int, input().split()))
	i = 0
	sol = []
	val = 0
	for j in range(1, n - 1):
		if A[j] > A[j - 1] and A[j] > A[j + 1]:
			val += (j - i + 1) * (j - i + 2) // 2
			val += -1
			i = j
	val += (n - i) * (n - i + 1) // 2
	ans.append(val)
print(*ans, sep='\n')


for _ in range(int(input())):
	n = int(input())
	l = [int(i) for i in input().split()]
	b = [1]
	for i in range(1, n - 1):
		if l[i] > l[i + 1]:
			if l[i] > l[i - 1]:
				b.append(i + 1)
	b.append(n)
	ans = 0
	for i in range(1, len(b)):
		temp = b[i] - b[i - 1] + 1
		ans += temp * (temp + 1) // 2
	print(ans - (len(b) - 2))


t = int(input())
for i in range(t):
	n = int(input())
	a = [abs(int(x)) for x in input().split()]
	sets = []
	lflag = False
	start = 0
	for end in range(n - 1):
		if not lflag:
			if a[end] < a[end + 1]:
				lflag = True
		elif a[end] > a[end + 1]:
			sets.append([start, end])
			temp = end
			while a[temp] == a[end]:
				start = temp
				temp -= 1
			lflag = False
	sets.append([start, n - 1])
	ans = 0
	for i in range(len(sets)):
		l = sets[i][1] - sets[i][0] + 1
		ans += l * (l + 1) / 2
		if i < len(sets) - 1 and sets[i + 1][0] <= sets[i][1]:
			l = sets[i][1] - sets[i + 1][0] + 1
			ans -= l * (l + 1) / 2
	print(int(ans))


t = int(input())
while t != 0:
	n = int(input())
	a = list(map(int, input().split()))
	if n == 1:
		print(1)
	else:
		ord1 = [0] * (n - 1)
		sum1 = 0
		for i in range(0, n - 1):
			if a[i] < a[i + 1]:
				ord1[i] = 1
			else:
				ord1[i] = 0
		cur = ord1[0]
		j = 0
		counts = [0] * n
		counts[0] = 1
		for i in range(0, n - 1):
			if ord1[i] == cur:
				counts[j] += 1
			elif cur == 0:
				cur = 1
				counts[j] += 1
			else:
				j = j + 1
				counts[j] = 2
				cur = 0
		k = 0
		for i in range(0, n):
			m = counts[i]
			if m > 0:
				sum1 += m * (m + 1) // 2
				k = k + 1
		k = k - 1
		print(sum1 - k)
	t = t - 1


for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	dp = []
	dp.append(1)
	for i in range(1, n - 1):
		if a[i] > a[i - 1] and a[i] > a[i + 1]:
			dp.append(i + 1)
	dp.append(n)
	ans = 0
	for i in range(1, len(dp)):
		c = dp[i] - dp[i - 1] + 1
		ans += c * (c + 1) // 2
	ans -= len(dp) - 2
	print(ans)


t = int(input())
for x in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	ls = [1]
	for i in range(1, n - 1):
		if arr[i] > arr[i - 1] and arr[i] > arr[i + 1]:
			ls.append(i + 1)
	ls.append(n)
	ans = 0
	cnt = 0
	for i in range(1, len(ls)):
		cnt = ls[i] - ls[i - 1] + 1
		ans += cnt * (cnt + 1) // 2
	ans -= len(ls) - 2
	print(ans)


for _ in range(int(input())):
	ans = 0
	n = int(input())
	ls = list(map(int, input().split(' ')))
	ls.insert(0, 0)
	ls.append(0)
	t = 0
	ct = 0
	for i in range(n + 2):
		if i == 0 or i == n + 1:
			continue
		if ls[i - 1] < ls[i] and ls[i] > ls[i + 1]:
			t = t + 1
			ct = ct + 1
			ans = ans + t * (t + 1) // 2
			t = 1
		else:
			t = t + 1
	ans = ans + t * (t + 1) // 2
	print(ans - ct)


testc = int(input())
for q in range(testc):
	n = int(input())
	a = list(map(int, input().split()))
	l = [1]
	for i in range(1, n - 1):
		if a[i] > a[i - 1] and a[i] > a[i + 1]:
			l.append(i + 1)
	l.append(n)
	ans = 0
	x = len(l)
	for i in range(1, x):
		c = l[i] - l[i - 1] + 1
		ans += c * (c + 1) // 2
	ans -= x - 2
	print(ans)


for _ in range(int(input())):
	n = int(input())
	li = list(map(int, input().split()))
	liDiff = []
	last = 0
	count = 0
	for i in li:
		if i >= last:
			count += 1
		else:
			liDiff.append(count)
			count = 1
		last = i
	liDiff.append(count)
	liNew = []
	count = 0
	for i in range(len(liDiff)):
		if liDiff[i] == 1:
			count += 1
		else:
			if i != 0 and i - count != 0:
				liNew.append(liDiff[i] + count + 1)
			else:
				liNew.append(liDiff[i] + count)
			count = 0
	if count > 0:
		if count == len(liDiff):
			liNew.append(count)
		else:
			liNew.append(count + 1)
	ans = 0
	for i in liNew:
		ans = ans + i * (i + 1) // 2
	ans += n - sum(liNew)
	print(ans)


for _ in range(int(input())):
	N = int(input())
	P = list(map(int, input().split()))
	if N == 1:
		print(1)
	elif N == 2:
		print(3)
	else:
		l = ['D' if i == 0 or P[i] < P[i - 1] else 'I' for i in range(N)]
		inI = False
		nDs = nIs = 0
		ans = 0
		for c in l:
			if c == 'D':
				if inI:
					inI = False
					(nDs, nIs) = (1, 0)
				nDs += 1
				ans += nDs
				inI = False
			else:
				nIs += 1
				ans += nDs + nIs
				inI = True
		print(ans)


T = int(input())
while T > 0:
	n = int(input())
	a = [int(item) for item in input().split()]
	v = [1]
	for i in range(1, n - 1):
		if a[i] > a[i - 1] and a[i] > a[i + 1]:
			v.append(i + 1)
	v.append(n)
	ans = 0
	cnt = 0
	for i in range(1, len(v)):
		cnt = v[i] - v[i - 1] + 1
		ans += cnt * (cnt + 1) // 2
	ans -= len(v) - 2
	print(ans)
	T -= 1


def solve(n, arr):
	if n == 1:
		return 1
	tmp = []
	lst = []
	res = 0
	for i in range(1, n):
		tmp.append(arr[i] < arr[i - 1])
	lst.append([tmp[0], 1])
	for i in range(1, len(tmp)):
		if tmp[i] == lst[len(lst) - 1][0]:
			lst[len(lst) - 1][1] += 1
		else:
			lst.append([tmp[i], 1])
	lst.append([0, 0])
	for i in range(len(lst) - 1):
		res += lst[i][1] * (lst[i][1] + 1) // 2
	for i in range(len(lst) - 1):
		if lst[i][0] == 1:
			res += lst[i][1] * lst[i + 1][1]
	return res + n
t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	print(solve(n, arr))