Given an array $A_1, A_2, ..., A_N$, count the number of subarrays of array $A$ which are non-decreasing.

A subarray $A[i, j]$, where $1 ≤ i ≤ j ≤ N$ is a sequence of integers $A_i, A_i+1, ..., A_j$.
A subarray $A[i, j]$ is non-decreasing if $A_i ≤ A_i+1 ≤ A_i+2 ≤ ... ≤ A_j$. You have to count the total number of such subarrays.

-----Input-----
- 
The first line of input contains an 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$ denoting the size of array.
- 
The second line contains $N$ space-separated integers $A_1$, $A_2$, …, $A_N$ denoting the elements of the array.

-----Output-----
For each test case, output in a single line the required answer.

-----Constraints-----
- $1 ≤ T ≤ 5$
- $1 ≤ N ≤ 10^5$
- $1 ≤ A_i ≤ 10^9$

-----Subtasks-----
- Subtask 1 (20 points) : $1 ≤ N ≤ 100$
- Subtask 2 (30 points) : $1 ≤ N ≤ 1000$
- Subtask 3 (50 points) : Original constraints

-----Sample Input:-----
2
4
1 4 2 3
1
5

-----Sample Output:-----
6
1

-----Explanation-----
Example case 1.

All valid subarrays are $A[1, 1], A[1, 2], A[2, 2], A[3, 3], A[3, 4], A[4, 4]$.

Note that singleton subarrays are identically non-decreasing.
Example case 2.

Only single subarray $A[1, 1]$ is non-decreasing.

Source: codechef | Difficulty: MEDIUM
Tags: Dynamic programming

Combinatorics

Mathematics


Solutions:
t = int(input())
for i in range(t):
	N = int(input())
	st = input().split()
	L = []
	for x in st:
		L.append(int(x))
	n = 1
	cnt = 1
	for p in range(1, N):
		if L[p] < L[p - 1]:
			n += 1
			cnt = 1
		else:
			cnt += 1
			n += cnt
		p += 1
	print(n)


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	(c, res) = (1, 1)
	for i in range(1, n):
		if a[i - 1] <= a[i]:
			c += 1
		else:
			c = 1
		res += c
	print(res)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	c = 1
	m = []
	for i in range(n - 1):
		if a[i] <= a[i + 1]:
			c += 1
		else:
			m.append(c)
			c = 1
	if c != 0:
		m.append(c)
	z = n
	for i in m:
		z += i * (i - 1) // 2
	print(z)


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


t = int(input())
for _ in range(t):
	a = int(input())
	lst = list(map(int, input().split()))
	dp = [1] * a
	count = 1
	for i in range(a - 2, -1, -1):
		if lst[i] <= lst[i + 1]:
			dp[i] = dp[i + 1] + 1
		count += dp[i]
	print(count)


for i in range(int(input())):
	a = int(input())
	l = list(map(int, input().split()))
	(s, r) = (0, 1)
	for i in range(a - 1):
		if l[i] <= l[i + 1]:
			s += r + 1
			r += 1
		else:
			r = 1
			s += 1
	print(s + 1)


x = int(input())
for i in range(x):
	y = int(input())
	l = list(map(int, input().split()))
	c = [1] * y
	for j in range(y - 1):
		if l[j] <= l[j + 1]:
			c[j + 1] = c[j] + 1
	print(sum(c))


def su(i):
	return i * (i + 1) // 2
i = int(input())
listk = []
for _ in range(i):
	kk = int(input())
	k = input().split()
	k2 = []
	for i in k:
		k2.append(int(i))
	imp = []
	st = 0
	for i in range(len(k2) - 1):
		if k2[i] > k2[i + 1]:
			imp.append(k2[st:i + 1])
			st = i + 1
		if i == len(k2) - 2:
			imp.append(k2[st:])
	tot = 0
	for ele in imp:
		tot = tot + su(len(ele))
	if len(k2) == 1:
		tot = 1
	listk.append(tot)
for ele in listk:
	print(ele)


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


for i in range(int(input())):
	n = int(input())
	l = [int(x) for x in input().split()]
	count = 0
	sumv = 0
	for i in range(n):
		count += 1
		if i != n - 1 and l[i] > l[i + 1]:
			sumv += int((count + 1) * count / 2)
			count = 0
	sumv += int((count + 1) * count / 2)
	print(sumv)


def count_subarrays(arr):
	n = len(arr)
	dp = [0] * n
	dp[0] = 1
	for i in range(1, n):
		if arr[i] >= arr[i - 1]:
			dp[i] = dp[i - 1] + 1
		else:
			dp[i] = 1
	return sum(dp)
t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	print(count_subarrays(arr))


for _ in range(int(input())):
	n = int(input())
	x = list(map(int, input().split()))
	cnt = 0
	for i in range(0, n):
		for j in range(i, n):
			s = x[i:j + 1]
			t = x[i:j + 1]
			s.sort()
			if s == t:
				cnt = cnt + 1
	print(cnt)


t = int(input())
for i in range(t):
	n = int(input())
	ar = list(map(int, input().split()))
	tot = 0
	st = 0
	for j in range(1, n):
		if ar[j - 1] > ar[j]:
			si = j - st
			c = si * (si + 1) // 2
			tot += c
			st = j
	si = n - st
	c = si * (si + 1) // 2
	tot += c
	print(tot)


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


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


for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	c = 1
	x = 1
	for i in range(1, n):
		if a[i - 1] <= a[i]:
			c += 1
		else:
			c = 1
		x += c
	print(x)


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


tkln = int(input())
for i in range(tkln):
	n = int(input())
	arrkln = list(map(int, input().split()))
	count = 1
	ans = 0
	for i in range(1, n):
		if arrkln[i - 1] <= arrkln[i]:
			count += 1
		else:
			ans += count * (count + 1) // 2
			count = 1
	ans += count * (count + 1) // 2
	print(ans)


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


for _ in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split()]
	a.append(-1)
	s = 0
	(i, j, c) = (0, 1, 0)
	while j < len(a):
		if a[j] < a[j - 1]:
			s += (j - i) * (1 + j - i) / 2
			i = j
		j += 1
	print(int(s))


T = int(input())
for _ in range(T):
	N = int(input())
	A = list(map(int, input().split()))
	dp = [1] * N
	for i in range(1, N):
		if A[i] >= A[i - 1]:
			dp[i] = dp[i - 1] + 1
	print(sum(dp))


import sys

def iinput():
	return int(sys.stdin.readline().strip())

def get_list():
	return list(map(int, sys.stdin.readline().strip().split()))
for _ in range(iinput()):
	n = iinput()
	c = 0
	t = get_list()
	l = [1] * n
	for i in range(1, n):
		if t[i - 1] <= t[i]:
			l[i] += l[i - 1]
	print(sum(l))