Utkarsh has a [permutation] P of \{0, 1, 2, \dots, N-1\}.

He wants to find the number of pairs (L, R) (1 ≤ L < R ≤ N) such that swapping the elements P_{L} and P_{R} does not change the [MEX] of any [subarray].

Formally, find the number of pairs (L, R) (1≤ L < R ≤ N) satisfying the following condition:
Let P' be the permutation defined as follows:
- P'_i = P_{i} for i \in \{1, 2, 3, \ldots, N}\setminus \{L, R\}
- P'_L = P_{R}
- P'_R = P_{L}
mex(\{P_{i}, P_{i+1}, \ldots, P_{j}\}) = mex(\{P'_i, P'_{i+1}, \ldots, P'_j\}) for every 1 ≤ i ≤ j ≤ N

For example, let N = 7 and P = [2, 5, 1, 0, 3, 6, 4]. Then,
Swapping the pair (1, 3), i.e swapping P_{1} = 2 and P_{3} = 1 would give us the permutation P' = [1, 5, 2, 0, 3, 6, 4]. This changes the mex of the subarray [3, 4], because mex(\{P_{3}, P_{4}\}) = mex(\{1, 0\}) = 2 but mex(\{P'_3, P'_4\}) = mex(\{2, 0\}) = 1, so (1, 3) is not a valid swap.
Swapping the pair (4, 7) gives us the permutation P' = [2, 5, 1, 4, 3, 6, 0]. This changes the mex of the subarray [7, 7] — mex(\{P_{7}\}) = mex(\{4\}) = 0 and mex(\{P'_7\}) = mex(\{0\}) = 1. So, (4, 7) is also not a valid pair.
However, it can be verified that the pair (2, 6) is valid — swapping P_{2} and P_{6} gives us the permutation P' = [2, 6, 1, 0, 3, 5, 4], and mex(P[i \ldots j]) = mex(P'[i \ldots j]) for every 1 ≤ i ≤ j ≤ 7.

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

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

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

For each test case, output on a new line the number of pairs (L,R) such that swapping P_{L} and P_{R} does not change the MEX of any subarray.

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

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

----- Sample Input 1 ------ 
2
4
0 1 2 3
7
2 5 1 0 3 6 4

----- Sample Output 1 ------ 
0
1

----- explanation 1 ------ 
Test case $1$: There are no valid pairs.

Test case $2$: There is only one valid pair, $(L,R) = (2,6)$, i.e, swapping $P_{2} = 5$ and $P_{6} = 6$ to obtain the permutation $[2, 6, 1, 0, 3, 5, 4]$.

Difficulty: VERY_HARD
Tags: Greedy algorithms
Skill types: Greedy algorithms

Starter code:

Solutions:
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	pos = [0 for i in range(n)]
	for i in range(n):
		pos[l[i]] = i
	l = pos[0]
	r = pos[0]
	ans = 0
	for i in range(1, n):
		cu = pos[i]
		if cu >= l and cu <= r:
			ans += r - l - i
		elif cu < l:
			l = cu
		else:
			r = cu
	print(ans)


t = int(input())
for i in range(t):
	n = int(input())
	line = input()
	P = line.split()
	indexs = []
	for i in range(n):
		indexs.append(0)
	for i in range(n):
		indexs[int(P[i])] = i
	index0 = indexs[0]
	index1 = indexs[1]
	min_ind = min(index0, index1)
	max_ind = max(index0, index1)
	total_pair = 0
	for i in range(2, n):
		index_i = indexs[i]
		if index_i < min_ind:
			min_ind = index_i
		elif index_i > max_ind:
			max_ind = index_i
		else:
			pairable = max_ind - min_ind - i
			total_pair += pairable
	print(total_pair)


import sys
import bisect
from bisect import bisect_left as lb
from bisect import bisect_right as rb
from queue import PriorityQueue
from queue import Queue
input_ = lambda : sys.stdin.readline().strip('\r\n')
from math import log
from math import gcd
from math import atan2, acos
from random import randint
import random
sa = lambda : input_()
sb = lambda : int(input_())
sc = lambda : input_().split()
sd = lambda : list(map(int, input_().split()))
sflo = lambda : list(map(float, input_().split()))
se = lambda : float(input_())
sf = lambda : list(input_())
flsh = lambda : sys.stdout.flush()
mod = 10 ** 9 + 7
mod1 = 998244353
gp = []
cost = []
dp = []
mx = []
ans1 = []
ans2 = []
special = []
specnode = []
a = 0
kthpar = []

def dfs2(root, par):
	if par != -1:
		dp[root] = dp[par] + 1
	for i in range(1, 20):
		if kthpar[root][i - 1] != -1:
			kthpar[root][i] = kthpar[kthpar[root][i - 1]][i - 1]
	for child in gp[root]:
		if child == par:
			continue
		kthpar[child][0] = root
		dfs(child, root)
ans = 0
a = []
(n, k) = (0, 0)
b = []
vis = []
tot = 0
time = []
time1 = []
adj = []
mx = -1
eps = 1e-07
gp = []
ans = []

def update_it(bit, i, val):
	n = len(bit)
	while i < n:
		bit[i] += val
		i += i & -i

def get_ans(bit, i):
	n = len(bit)
	tot = 0
	while i > 0:
		tot += bit[i]
		i -= i & -i
	return tot

def flip(a, l, r):
	for i in range(l, r):
		a[i] = '0' if a[i] == '1' else '1'
	return

def hnbhai(tc):
	n = sb()
	a = sd()
	prefix = [0] * (n + 1)
	strt = a.index(0)
	end = a.index(0)
	for i in range(n):
		prefix[a[i]] = i
	inregion = 0
	ans = 0
	for i in range(1, n):
		if prefix[i] > end:
			ans += inregion * (end - strt + 1 - i)
			end = prefix[i]
			ans += inregion * (inregion - 1) // 2
			inregion = 0
			continue
		if prefix[i] < strt:
			ans += inregion * (end - strt + 1 - i)
			strt = prefix[i]
			ans += inregion * (inregion - 1) // 2
			inregion = 0
			continue
		inregion += 1
	ans += inregion * (inregion - 1) // 2
	print(ans)
	return
for _ in range(sb()):
	hnbhai(_ + 1)