You are given a sequence $A_1, A_2, \ldots, A_N$. Calculate the number of ways to remove a non-empty contiguous subsequence from it such that the resulting sequence is non-empty and strictly increasing.

-----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-separated integers $A_1, A_2, \ldots, A_N$.

-----Output-----
For each test case, print a single line containing one integer ― the number of ways.

-----Constraints-----
- $1 \le T \le 10$
- $1 \le N \le 10^5$
- $|A_i| \le 10^9$ for each valid $i$

-----Subtasks-----
Subtask #1 (40 points): $N \le 1,000$
Subtask #2 (60 points): original constraints

-----Example Input-----
2
3
1 1 2
4
2 4 3 5

-----Example Output-----
4
7

Source: codechef | Difficulty: HARD
Tags: Combinatorics

Data structures


Solutions:
t = int(input())
for _ in range(t):
	n = int(input())
	data = list(map(int, input().strip().split()))
	prefix = [False] * n
	suffix = [False] * n
	prefix[0] = True
	for i in range(1, n):
		if data[i] > data[i - 1]:
			prefix[i] = True
		else:
			break
	suffix[n - 1] = True
	for i in range(n - 2, -1, -1):
		if data[i] < data[i + 1]:
			suffix[i] = True
		else:
			break
	ans = 0
	if prefix.count(True) == n:
		ans = n * (n - 1) / 2 + (n - 1)
	else:
		for i in range(n):
			if prefix[i]:
				low = i
				high = n
				while high - low > 1:
					mid = (low + high) // 2
					if suffix[mid] and data[i] < data[mid]:
						high = mid
					else:
						low = mid
				ans += n - high
			else:
				break
		ans += suffix.count(True)
		ans += prefix.count(True)
	print(int(ans))


def dels(a, n):
	fin = []
	fin1 = []
	for i in range(n):
		if a[i] < a[i + 1]:
			fin1.append(i)
		else:
			fin1.append(i)
			fin.append(fin1)
			fin1 = []
	if len(fin) == 1:
		return n * (n + 1) // 2 - 1
	lptr = len(fin[0])
	rptr = fin[-1][0]
	temp = n
	res = 0
	res += lptr + (n - rptr)
	while temp >= rptr + 1 and lptr > 0:
		if a[lptr - 1] >= a[temp - 1]:
			lptr -= 1
			continue
		res += lptr
		temp -= 1
	return res
t = int(input())
f = -(10 ** 9 + 1)
while t:
	t -= 1
	n = int(input())
	a = list(map(int, input().split()))
	a.append(f)
	print(dels(a, n))


t = int(input())
i = 0
while i < t:
	n = int(input())
	a = list(map(int, input().split()))
	j = 1
	leftend = 0
	while j < n and a[j] > a[j - 1]:
		leftend += 1
		j += 1
	rightend = n - 1
	j = n - 2
	while j >= 0 and a[j] < a[j + 1]:
		j -= 1
		rightend -= 1
	if n == 1:
		print(0)
	elif rightend == 0 and leftend == n - 1:
		print(int(n * (n - 1) / 2 + n - 1))
	else:
		k = 0
		s = 0
		while k <= leftend:
			l = rightend
			posi = 0
			notFound = True
			while l < n and notFound:
				if a[l] > a[k]:
					posi = l
					notFound = False
				l += 1
			if notFound:
				s += n - l + 1
			if not notFound:
				s += n - posi + 1
			k += 1
		s += n - rightend
		print(s)
	i += 1


T = int(input())
while T > 0:
	n = int(input())
	a = list(map(int, input().split()))
	prefix = [True for k in range(n)]
	suffix = [True for k in range(n)]
	for i in range(1, n):
		prefix[i] = prefix[i - 1] and a[i] > a[i - 1]
	for i in range(n - 2, -1, -1):
		suffix[i] = suffix[i + 1] and a[i] < a[i + 1]
	lo = 0
	hi = n - 1
	while lo < hi:
		mid = (lo + hi) // 2
		if suffix[mid]:
			hi = mid
		else:
			lo = mid + 1
	ans = n - lo
	for i in range(n - 1):
		if prefix[i]:
			lo = i + 1
			hi = n - 1
			while lo < hi:
				mid = (lo + hi) // 2
				if suffix[mid] and a[mid] > a[i]:
					hi = mid
				else:
					lo = mid + 1
			ans += n - lo + 1
			if lo == i + 1 or (lo == n - 1 and a[lo] < a[i]):
				ans -= 1
		else:
			break
	if prefix[-1]:
		ans -= 1
	print(ans)
	T -= 1


T = int(input())

def bSearch(A, suff, k, i, j):
	if i >= len(A):
		return
	if i == j:
		if suff[i] == False or A[j] <= A[k]:
			return
		return i
	mid = (i + j) // 2
	if mid <= k:
		return bSearch(A, suff, k, mid + 1, j)
	elif A[mid] <= A[k] or suff[mid] == False:
		return bSearch(A, suff, k, mid + 1, j)
	else:
		return bSearch(A, suff, k, i, mid)
for _ in range(T):
	N = int(input())
	A = list(map(int, input().split()))
	pref = [False for _ in range(N)]
	suff = [False for _ in range(N)]
	pref[0] = True
	suff[-1] = True
	for i in range(1, N):
		if A[i] > A[i - 1]:
			pref[i] = True
		else:
			break
	for i in reversed(range(N - 1)):
		if A[i] < A[i + 1]:
			suff[i] = True
		else:
			break
	count = 0
	for i in range(N):
		if pref[i] == True:
			j = bSearch(A, suff, i, i + 1, N - 1)
			if j == None:
				if i < N - 1:
					count += 1
			elif j == i + 1:
				count += N - j
			else:
				count += N - j + 1
	for i in range(1, N):
		if suff[i] == True:
			count += 1
	print(count)


for _t in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	if all((a[i] < a[i + 1] for i in range(n - 1))):
		print(n * (n + 1) // 2 - 1)
		continue
	for i in range(1, n):
		if a[i - 1] >= a[i]:
			sorted_beg = a[:i]
			break
	for i in range(n - 1, 0, -1):
		if a[i - 1] >= a[i]:
			sorted_end = a[i:]
			break
	numways = len(sorted_beg) + len(sorted_end)
	le = len(sorted_end)
	for beg in sorted_beg:
		try:
			while sorted_end[0] <= beg:
				del sorted_end[0]
				le -= 1
		except IndexError:
			break
		numways += le
	print(numways)


def bin(arr, l, r, val, n):
	ans = n
	while l <= r:
		mid = (l + r) // 2
		if arr[mid] <= val:
			l = mid + 1
		else:
			ans = mid
			r = mid - 1
	return ans
t = int(input())
while t:
	n = int(input())
	arr = list(map(int, input().strip().split(' ')))
	pre = []
	suff = [0] * n
	pre.append(1)
	for i in range(1, n):
		if arr[i] > arr[i - 1] and pre[i - 1] == 1:
			pre.append(1)
		else:
			pre.append(0)
	flag = 0
	temp = 0
	for i in range(n - 1, -1, -1):
		if i == n - 1:
			suff[i] = 1
		elif arr[i] < arr[i + 1] and suff[i + 1] == 1:
			suff[i] = 1
		elif flag == 0:
			temp = i + 1
			suff[i] = 0
			flag = 1
		else:
			suff[i] = 0
	count = 0
	y = n
	for i in range(n):
		y = n
		if pre[i] == 1:
			count += 1
			if temp > i + 1:
				y = bin(arr, temp, n - 1, arr[i], n)
			elif i + 2 < n:
				y = bin(arr, i + 2, n - 1, arr[i], n)
			count += n - y
	count += n - temp
	if pre[temp] == 1:
		count -= 2
	print(count)
	t -= 1


import bisect
for t in range(int(input())):
	n = int(input())
	arr = [int(a) for a in input().split()]
	prifix = list()
	prefix = [False for _ in range(n)]
	for i in range(0, n):
		if i == 0:
			prefix[i] = True
		elif arr[i] > arr[i - 1]:
			prefix[i] = True
		else:
			break
	sufix = list()
	sufix = [False for _ in range(n)]
	for i in range(n - 1, -1, -1):
		if i == n - 1:
			sufix[i] = True
		elif arr[i] < arr[i + 1]:
			sufix[i] = True
		else:
			break
	left = 0
	right = 0
	for i in range(n):
		if prefix[i] == True:
			left = i
	for i in range(n - 1, -1, -1):
		if sufix[i] == True:
			right = i
	ans = 0
	if right == 0 and left == n - 1:
		ans = n * (n + 1) // 2 - 1
	else:
		i = 0
		while prefix[i] == True:
			if arr[i] > arr[n - 1]:
				ans += 1
			else:
				k = bisect.bisect_left(arr, arr[i], right, n - 1)
				ans += n - k + 1
				if arr[k] == arr[i]:
					ans -= 1
			i += 1
		ans += n - right
	print(ans)


import sys, bisect
sys.setrecursionlimit(10 ** 9)
t = int(input())
for _ in range(t):
	n = int(input())
	it = list(map(int, input().split()))
	if n == 1:
		print(0)
		continue
	if n == 2:
		print(2)
		continue
	if n > 2:
		ss = [[0]]
		for i in range(1, n):
			if it[i] > it[i - 1]:
				ss[-1].append(i)
			else:
				ss.append([i])
		if len(ss) == 1:
			print(n * (n - 1) // 2 + n - 1)
			continue
		tot = 0
		ind = len(ss[0]) - 1
		ind2 = len(ss[-1]) - 1
		aa = ss[0]
		bb = ss[-1]
		tot = 0
		while ind >= 0 and ind2 >= 0:
			if it[bb[ind2]] > it[aa[ind]]:
				tot += ind + 1
				ind2 -= 1
			else:
				ind -= 1
		tot += len(aa)
		tot += len(bb)
		print(tot)


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


for _ in range(int(input())):
	n = int(input())
	seq = list(map(int, input().split()))
	(pref, suff) = (0, n - 1)
	for i in range(1, n):
		if seq[i] > seq[i - 1]:
			pref = i
		else:
			break
	for i in range(n - 2, -1, -1):
		if seq[i] < seq[i + 1]:
			suff = i
		else:
			break
	(l, r, ans) = (0, suff, 0)
	while r < n and l <= pref:
		if seq[l] < seq[r]:
			ans += n - r
			l += 1
		else:
			r += 1
	if suff < pref:
		print(n * (n - 1) // 2 + n - 1)
		continue
	print(ans + (pref + 1) + (n - suff))


for t in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	first_index = 0
	last_index = 0
	curr_index = 0
	indexes = [[0, 0]]
	for i in range(1, n):
		if a[i] > a[i - 1]:
			last_index = i
		else:
			indexes[curr_index][1] = last_index
			curr_index += 1
			last_index += 1
			first_index = last_index
			indexes.append([first_index, last_index])
	indexes[curr_index][1] = last_index
	res = 0
	if len(indexes) > 1:
		res = indexes[0][1] - indexes[0][0] + 1
		res += indexes[-1][1] - indexes[-1][0] + 1
		first_range_last_index = indexes[0][1]
		last_range_first_index = indexes[-1][0]
		n -= 1
		while first_range_last_index >= 0 and n >= last_range_first_index:
			if a[n] <= a[first_range_last_index]:
				res += len(a) - (n + 1)
				first_range_last_index -= 1
			else:
				n -= 1
		if first_range_last_index >= 0:
			res += (first_range_last_index + 1) * (len(a) - (n + 1))
	else:
		res = n * (n + 1) // 2 - 1
	print(res)


import bisect

def pre(a):
	for p in range(n - 1):
		if a[p] >= a[p + 1]:
			return p
	return n - 1

def suf(a):
	for s in range(1, n):
		if a[n - s] <= a[n - s - 1]:
			return n - s
	return 0
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	p = pre(a)
	s = suf(a)
	b = a[s:n]
	count = 0
	for i in range(p + 1):
		k = bisect.bisect(b, a[i])
		k += s
		count += n - k + 1
	if s == 0:
		print(n * (n + 1) // 2 - 1)
	else:
		print(count + n - s)


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	front = [0 for i in range(n)]
	back = [n - 1 for i in range(n)]
	for i in range(1, n):
		if front[i - 1] == i - 1 and arr[i] > arr[i - 1]:
			front[i] = i
		else:
			front[i] = front[i - 1]
	for i in range(n - 2, -1, -1):
		if back[i + 1] == i + 1 and arr[i] < arr[i + 1]:
			back[i] = i
		else:
			back[i] = back[i + 1]
	if back[0] == 0:
		print(2 * n - 2 + (n - 2) * (n - 1) // 2)
	else:
		ans = n - back[0]
		for i in range(1, n):
			if front[i - 1] == i - 1:
				ans += 1
				key = arr[i - 1]
				low = back[i]
				high = n - 1
				if arr[high] > key:
					flag = False
					while low < high:
						mid = (low + high) // 2
						if arr[mid] > key:
							high = mid
						else:
							low = mid
						if low + 1 == high:
							if flag:
								high -= 1
							flag = True
					mid = (low + high) // 2
					if arr[mid] <= key:
						mid += 1
					ans += n - mid
		print(ans)


from sys import stdin
input = stdin.readline
for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	if all((a[i] < a[i + 1] for i in range(n - 1))):
		print(n * (n + 1) // 2 - 1)
		continue
	for i in range(1, n):
		if a[i - 1] >= a[i]:
			arr1 = a[:i]
			break
	for j in range(n - 1, 0, -1):
		if a[j - 1] >= a[j]:
			arr2 = a[j:]
			break
	ans = len(arr1) + len(arr2)
	le = len(arr2)
	x = 0
	for i in arr1:
		while x < len(arr2) and arr2[x] <= i:
			x += 1
			le -= 1
		if x == len(arr2):
			break
		ans += le
	print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	e = n - 1
	for i in range(n - 2, -1, -1):
		if a[i + 1] > a[i]:
			e = i
		else:
			break
	cnt = 0
	for i in range(n):
		if i - 2 >= 0 and a[i - 2] >= a[i - 1]:
			break
		if e <= i:
			e = i + 1
		while e < n and i - 1 >= 0 and (a[i - 1] >= a[e]):
			e += 1
		cnt += n - e + 1
	print(cnt - 1)


def bin_search1(arr, x):
	s = 0
	e = len(arr) - 1
	while s <= e:
		m = (s + e) // 2
		if arr[m] > x:
			e = m - 1
		else:
			s = m + 1
	return s

def bin_search2(arr, x):
	s = 0
	e = len(arr) - 1
	while s <= e:
		m = (s + e) // 2
		if arr[m] >= x:
			e = m - 1
		else:
			s = m + 1
	return s
t = int(input())
for i in range(t):
	n = int(input())
	arr = [int(j) for j in input().split()]
	var = 0
	flag = 0
	for i in range(n - 1):
		if arr[i + 1] <= arr[i]:
			var = 1
			ind1 = i
			break
	if var == 0:
		print(n * (n + 1) // 2 - 1)
		continue
	for i in range(n - 1, 0, -1):
		if arr[i - 1] >= arr[i]:
			ind2 = i
			break
	arr1 = arr[:ind1 + 1]
	arr2 = arr[ind2:]
	count = len(arr1) + len(arr2)
	for i in range(len(arr1)):
		x = bin_search1(arr2, arr1[i])
		count += len(arr2) + 1 - x
	for i in range(len(arr2)):
		x = bin_search1(arr1, arr2[i])
		count += x + 1
	print(count // 2)


for _ in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split()]
	i = 0
	while i < n - 1 and a[i] < a[i + 1]:
		i += 1
	j = n - 1
	while j > 0 and a[j - 1] < a[j]:
		j -= 1
	if i == n - 1:
		assert j == 0
		print(n * (n + 1) // 2 - 1)
		continue
	assert i < j
	tot = n - j
	for k in range(0, i + 1):
		while j < n and a[j] <= a[k]:
			j = j + 1
		tot += n + 1 - j
	print(tot)


def bsearch(left, right, val, A):
	mid = (left + right) // 2
	if left == right:
		if A[left] <= val:
			return 10 ** 9 + 7
		else:
			return left
	elif A[mid] <= val:
		return bsearch(mid + 1, right, val, A)
	else:
		return min(bsearch(left, mid, val, A), mid)
for _ in range(int(input())):
	n = int(input())
	a = [int(s) for s in input().split()]
	(i, j) = (1, n - 2)
	while i < n and a[i] > a[i - 1]:
		i += 1
	i -= 1
	while j >= 0 and a[j] < a[j + 1]:
		j -= 1
	j += 1
	if i < j:
		ans = i + 1 + n - j
		for i1 in range(i + 1):
			i2 = bsearch(j, n - 1, a[i1], a)
			if i2 != 10 ** 9 + 7:
				ans += n - i2
		print(ans)
	else:
		print(n * (n + 1) // 2 - 1)


import io, sys, atexit, os
import math as ma
from sys import exit
from decimal import Decimal as dec
from itertools import permutations
from itertools import combinations

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

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

def nu():
	return int(input())

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

def lcm(x, y):
	gg = find_gcd(x, y)
	return x * y // gg
mm = 1000000007
yp = 0

def solve():
	t = nu()
	for tt in range(t):
		n = nu()
		a = li()
		fr = [0] * n
		back = [0] * n
		fr[0] = 1
		for i in range(1, n):
			if a[i] <= a[i - 1]:
				break
			fr[i] = 1
		back[n - 1] = 1
		for i in range(n - 2, -1, -1):
			if a[i] >= a[i + 1]:
				break
			back[i] = 1
		if back[0] == 1:
			print(2 * n - 2 + (n - 2) * (n - 1) // 2)
		else:
			bk = -1
			ans = 0
			for i in range(n - 1, -1, -1):
				if back[i] == 1:
					bk = i
			fg = -1
			op = bk
			ans += n - bk
			for i in range(n):
				if fr[i] == 0:
					fg = i - 1
					break
				while bk < n and a[i] >= a[bk]:
					bk += 1
				if bk == n:
					continue
				ans += n - bk
			ans += fg + 1
			print(ans)
solve()


import bisect
for _ in range(int(input())):
	N = int(input())
	A = list(map(int, input().split()))
	Arr = [0] * N
	Arr[-1] = N - 1
	z = 1
	for i in range(N - 2, -1, -1):
		if A[i] < A[i + 1]:
			Arr[i] = Arr[i + 1]
			if Arr[i] == N - 1:
				z += 1
		else:
			Arr[i] = i
	ans = Arr[0] + 1 + z
	if Arr[0] == N - 1:
		ans -= 2
	bi = [A[i] for i in range(N) if Arr[i] == N - 1]
	for i in range(Arr[0] == N - 1, N - (Arr[0] == N - 1)):
		if Arr[i] == Arr[0]:
			ans += z - bisect.bisect_right(bi, A[i])
		else:
			break
	print(ans)


t = int(input())
while t:
	n = int(input())
	arr = list(map(int, input().strip().split(' ')))
	pre = []
	suff = [0] * n
	pre.append(1)
	for i in range(1, n):
		if arr[i] > arr[i - 1] and pre[i - 1] == 1:
			pre.append(1)
		else:
			pre.append(0)
	flag = 0
	temp = 0
	for i in range(n - 1, -1, -1):
		if i == n - 1:
			suff[i] = 1
		elif arr[i] < arr[i + 1] and suff[i + 1] == 1:
			suff[i] = 1
		elif flag == 0:
			temp = i + 1
			suff[i] = 0
			flag = 1
		else:
			suff[i] = 0
	count = 0
	for i in range(n):
		if pre[i] == 1:
			count += 1
			for j in range(temp, n):
				if arr[j] > arr[i] and j > i + 1:
					count += n - j
					break
	count += n - temp
	if pre[temp] == 1:
		count -= 2
	print(count)
	t -= 1


t = int(input())
for _ in range(t):
	n = int(input())
	data = list(map(int, input().strip().split()))
	prefix = [False] * n
	suffix = [False] * n
	prefix[0] = True
	for i in range(1, n):
		if data[i] > data[i - 1]:
			prefix[i] = True
		else:
			break
	suffix[n - 1] = True
	for i in range(n - 2, -1, -1):
		if data[i] < data[i + 1]:
			suffix[i] = True
		else:
			break
	ans = 0
	if prefix.count(True) == n:
		ans = n * (n - 1) / 2 + (n - 1)
	else:
		for i in range(n):
			if prefix[i]:
				val = 0
				for j in range(n):
					if suffix[j] and data[j] > data[i]:
						val = j
						break
				if val != 0:
					ans += n - val
			else:
				break
		ans += suffix.count(True)
		ans += prefix.count(True)
	print(int(ans))