You are given a permutation $p_1, p_2, \ldots, p_n$ of length $n$ of numbers $0, \ldots, n - 1$. Count the number of subsegments $1 \leq l \leq r \leq n$ of this permutation such that $mex(p_l, p_{l+1}, \ldots, p_r) > med(p_l, p_{l+1}, \ldots, p_r)$.

$mex$ of $S$ is the smallest non-negative integer that does not occur in $S$. For example:

$mex({0, 1, 2, 3}) = 4$

$mex({0, 4, 1, 3}) = 2$

$mex({5, 4, 0, 1, 2}) = 3$

$med$ of the set $S$ is the median of the set, i.e. the element that, after sorting the elements in non-decreasing order, will be at position number $\left \lfloor{ \frac{|S| + 1}{2} } \right \rfloor$ (array elements are numbered starting from $1$ and here $\left \lfloor{v} \right \rfloor$ denotes rounding $v$ down.). For example:

$med({0, 1, 2, 3}) = 1$

$med({0, 4, 1, 3}) = 1$

$med({5, 4, 0, 1, 2}) = 2$

A sequence of $n$ numbers is called a permutation if it contains all the numbers from $0$ to $n - 1$ exactly once.


-----Input-----

The first line of the input contains a single integer $t$ $(1 \leq t \leq 10^4$), the number of test cases.

The descriptions of the test cases follow.

The first line of each test case contains a single integer $n$ ($1 \leq n \leq 2 \cdot 10^5$), the length of the permutation $p$.

The second line of each test case contains exactly $n$ integers: $p_1, p_2, \ldots, p_n$ ($0 \leq p_i \leq n - 1$), elements of permutation $p$.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.


-----Output-----

For each test case print the answer in a single line: the number of subsegments $1 \leq l \leq r \leq n$ of this permutation such that $mex(p_l, p_{l+1}, \ldots, p_r) > med(p_l, p_{l+1}, \ldots, p_r)$.


-----Examples-----

Input
8
1
0
2
1 0
3
1 0 2
4
0 2 1 3
5
3 1 0 2 4
6
2 0 4 1 3 5
8
3 7 2 6 0 1 5 4
4
2 0 1 3
Output
1
2
4
4
8
8
15
6


-----Note-----

The first test case contains exactly one subsegment and $mex({0}) = 1 > med({0}) = 0$ on it.

In the third test case, on the following subsegments: $[1, 0]$, $[0]$, $[1, 0, 2]$ and $[0, 2]$, $mex$ is greater than $med$.

In the fourth test case, on the following subsegments: $[0, 2]$, $[0]$, $[0, 2, 1]$ and $[0, 2, 1, 3]$, $mex$ greater than $med$.

Source: codeforces | Difficulty: HARD
Tags: Amortized analysis

Mathematics


Solutions:
for _ in range(int(input())):
	n = int(input())
	p = list(map(int, input().split()))
	pinv = [0] * n
	for i in range(n):
		pinv[p[i]] = i
	(idxmin, idxmax) = (pinv[0], pinv[0])
	ans = 1
	for w in range(2, n + 1):
		if w % 2 == 1:
			(idxmin, idxmax) = (min(idxmin, pinv[w // 2]), max(idxmax, pinv[w // 2]))
		ans += max(0, min(idxmin, n - w) - max(idxmax + 1 - w, 0) + 1)
	print(ans)


for _ in range(int(input())):
	n = int(input())
	t = list(map(int, input().split()))
	tinv = [0] * n
	for i in range(n):
		tinv[t[i]] = i
	(idxmin, idxmax) = (tinv[0], tinv[0])
	ans = 1
	for w in range(2, n + 1):
		if w % 2 == 1:
			(idxmin, idxmax) = (min(idxmin, tinv[w // 2]), max(idxmax, tinv[w // 2]))
		ans += max(0, min(idxmin, n - w) - max(idxmax + 1 - w, 0) + 1)
	print(ans)


import math
import heapq as hq
from collections import defaultdict
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	inv_arr = [0] * n
	ans = 0
	for i in range(n):
		inv_arr[arr[i]] = i
	(l, r) = (n + 10, -1)
	for w in range(1, n + 1):
		if w % 2 == 1:
			(l, r) = (min(l, inv_arr[w // 2]), max(r, inv_arr[w // 2]))
		ans += max(0, min(l, n - w) - max(0, r + 1 - w) + 1)
	print(ans)


def onec(n, l, r, k):
	if r - l + 1 > k:
		return 0
	f = max(0, r - k + 1)
	s = min(n - 1, l + k - 1)
	return s - f - k + 2

def one():
	n = int(input())
	p = list(map(int, input().split()))
	d = [None] * n
	for (i, e) in enumerate(p):
		d[e] = i
	l = d[0]
	r = d[0]
	s = 0
	for i in range(n):
		k = i + 1
		w = -(-k // 2)
		l = min(l, d[w - 1])
		r = max(r, d[w - 1])
		s += onec(n, l, r, k)
	print(s)
t = int(input())
for i in range(t):
	one()


for _ in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split()]
	pos = {}
	for i in range(len(a)):
		pos[a[i]] = i
	leftmost_number = pos[0]
	rightmost_number = pos[0]
	ans = 0
	for length in range(1, len(a) + 1):
		leftmost_number = min(leftmost_number, pos[(length - 1) // 2])
		rightmost_number = max(rightmost_number, pos[(length - 1) // 2])
		leftmost_start = max(0, rightmost_number - length + 1)
		rightmost_start = min(leftmost_number, n - length)
		ans += max(0, rightmost_start - leftmost_start + 1)
	print(ans)