Initially, Chef had an array A of length N. Chef performs the following operation on A at most once:
Select L and R such that 1 ≤ L ≤ R ≤ N and set A_{i} := A_{i} + 1 for all L ≤ i ≤ R.

Determine the maximum number of *inversions* Chef can decrease from the array A by applying the operation at most once.  
More formally, let the final array obtained after applying the operation at most once be B. You need to determine the maximum value of inv(A) - inv(B) (where inv(X) denotes the number of *inversions* in array X).

Note: The number of *inversions* in an array X is the number of pairs (i, j) such that 1 ≤ i < j ≤ N and X_{i} > X_{j}.

------ 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 array A.
- The second line of each test case contains N space-separated integers A_{1}, A_{2}, \dots, A_{N} denoting the array A.

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

For each test case, output the maximum value of inv(A) - inv(B) which can be obtained after applying at most one operation.

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

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

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

----- Sample Output 1 ------ 
2
0
3

----- explanation 1 ------ 
Test case $1$: The initial array $A$ is $[4, 2, 3, 1, 5]$ which has $5$ inversions. We can perform operation on $L = 3, R = 4$. The resultant array will be $[4, 2, 4, 2, 5]$ which has $3$ inversions. Therefore we reduce the number of inversion by $2$ which is the maximum decrement possible.

Test case $2$: The initial array $A$ is $[1, 2, 3, 4, 5, 6]$ which has $0$ inversions. In this case, we do not need to apply any operation and the final array $B$ will be same as the initial array $A$. Therefore the maximum possible decrement in inversions is $0$.

Test case $3$: The initial array $A$ is $[2, 1, 1, 1]$ which has $3$ inversions. We can perform operation on $L = 2, R = 4$. The resultant array will be $[2, 2, 2, 2]$ which has $0$ inversions. Therefore we reduce the number of inversion by $3$ which is the maximum decrement possible.

Difficulty: MEDIUM_HARD
Tags: Constructive algorithms

Data structures

Ad-hoc
Skill types: Data structures

Starter code:

Solutions:
def LII():
	return [int(x) for x in input().split()]
for _ in range(int(input())):
	n = int(input())
	a = LII()
	assert len(a) == n
	assert all((x >= 1 and x <= n for x in a))
	count_right = [0] * (n + 2)
	count_left = [0] * (n + 2)
	for x in a:
		count_right[x + 1] += 1
	delta_neg_invs = 0
	maxx = 0
	for x in a:
		delta_neg_invs += count_right[x] - count_left[x + 1]
		if delta_neg_invs > maxx:
			maxx = delta_neg_invs
		count_right[x + 1] -= 1
		count_left[x] += 1
	print(maxx)


AcHyTh = 0
TtT = int(input())
for i in range(TtT):
	NnN = int(input())
	AmZxx = [int(i) for i in input().split()]
	m = [0] * (NnN + 2)
	for i in AmZxx:
		if m[i] != 0:
			m[i] += 1
		else:
			m[i] = 1
	AmZx = [0] * (NnN + 2)
	lst = []
	ReSZaV = 0
	for i in range(NnN - 1, -1, -1):
		j = AmZxx[i]
		m[j] -= 1
		j += 1
		AmZx[j] += 1
		ReSZaV += m[AmZxx[i] + 1]
		ReSZaV -= AmZx[AmZxx[i]]
		lst.append(ReSZaV)
	print(max(lst))


T = int(input())
for i in range(T):
	N = int(input())
	l = [int(i) for i in input().split()]
	m = [0] * (N + 2)
	for i in l:
		if m[i] != 0:
			m[i] += 1
		else:
			m[i] = 1
	m2 = [0] * (N + 2)
	lst = []
	ans = 0
	for i in range(N - 1, -1, -1):
		j = l[i]
		m[j] -= 1
		j += 1
		m2[j] += 1
		ans += m[l[i] + 1]
		ans -= m2[l[i]]
		lst.append(ans)
	print(max(lst))


import math
case = int(input())
for _ in range(case):
	n = int(input())
	arr = list(map(int, input().split(' ')))
	leftmap = {}
	rightmap = {}
	for i in range(n):
		if arr[i] not in leftmap:
			leftmap[arr[i]] = 0
		leftmap[arr[i]] += 1
	inv = 0
	i = n - 1
	res = 0
	while i >= 0:
		if arr[i] + 1 in leftmap:
			inv += leftmap[arr[i] + 1]
		if arr[i] in rightmap:
			inv -= rightmap[arr[i]]
		res = max(res, inv)
		leftmap[arr[i]] -= 1
		if arr[i] + 1 not in rightmap:
			rightmap[arr[i] + 1] = 0
		rightmap[arr[i] + 1] += 1
		i -= 1
	print(res)


t = int(input())
for _ in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	pref = [0] * (n + 2)
	last = [0] * (n + 1)
	for i in l:
		last[i] += 1
	(index, m) = (0, 0)
	for i in l:
		index += last[i - 1]
		index -= pref[i + 1]
		pref[i] += 1
		last[i] -= 1
		m = max(m, index)
	print(m)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	pref_freq = [0] * (n + 2)
	suf_freq = [0] * (n + 2)
	for x in a:
		pref_freq[x] += 1
	ans = 0
	cur = 0
	for i in reversed(range(1, n)):
		cur -= pref_freq[a[i]] * suf_freq[a[i] - 1] + pref_freq[a[i] + 1] * suf_freq[a[i]]
		suf_freq[a[i]] += 1
		pref_freq[a[i]] -= 1
		cur += pref_freq[a[i]] * suf_freq[a[i] - 1] + pref_freq[a[i] + 1] * suf_freq[a[i]]
		ans = max(ans, cur)
	print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	suff = [0] * (n + 1)
	pref = [0] * (n + 2)
	for a in arr:
		suff[a] += 1
	(inv, max_inv) = (0, 0)
	for a in arr:
		inv += suff[a - 1]
		inv -= pref[a + 1]
		suff[a] -= 1
		pref[a] += 1
		max_inv = max(inv, max_inv)
	print(max_inv)


import random
import math
from collections import defaultdict, Counter, deque, OrderedDict
from heapq import heapify, heappush, heappop
from functools import lru_cache
from bisect import bisect_left, bisect_right
import sys
input = lambda : sys.stdin.readline().strip()

class SegmentTree:

	def __init__(self, arr, func=lambda x, y: x + y, defaultvalue=0):
		self.n = len(arr)
		self.segmentTree = [0] * self.n + arr
		self.func = func
		self.defaultvalue = defaultvalue
		self.buildSegmentTree(arr)

	def buildSegmentTree(self, arr):
		for i in range(self.n - 1, 0, -1):
			self.segmentTree[i] = self.func(self.segmentTree[2 * i], self.segmentTree[2 * i + 1])

	def query(self, l, r):
		l += self.n
		r += self.n
		res = self.defaultvalue
		while l < r:
			if l & 1:
				res = self.func(res, self.segmentTree[l])
				l += 1
			l >>= 1
			if r & 1:
				r -= 1
				res = self.func(res, self.segmentTree[r])
			r >>= 1
		return res

	def update(self, i, value):
		i += self.n
		self.segmentTree[i] = value
		while i > 1:
			i >>= 1
			self.segmentTree[i] = self.func(self.segmentTree[2 * i], self.segmentTree[2 * i + 1])

class UnionFind:

	def __init__(self, n):
		self.n = n
		self.parents = list(range(n))

	def find(self, x):
		if self.parents[x] == x:
			return x
		else:
			self.parents[x] = self.find(self.parents[x])
			return self.parents[x]

	def union(self, x, y):
		x = self.find(x)
		y = self.find(y)
		if x != y:
			self.parents[x] = y
dire = [0, 1, 0, -1, 0]

def is_prime(n):
	for i in range(2, int(n ** 0.5) + 1):
		if n % i == 0:
			return False
	return True

def ncr(n, r, p):
	num = den = 1
	for i in range(r):
		num = num * (n - i) % p
		den = den * (i + 1) % p
	return num * pow(den, p - 2, p) % p

def case(t):
	print('Case #{}:'.format(t), end=' ')
RANDOM = random.randrange(2 ** 62)

def Wrapper(x):
	return x ^ RANDOM

def solve():
	n = int(input())
	arr = list(map(int, input().split()))
	c = Counter(arr)
	mapp = Counter()
	ans = 0
	curr = 0
	for i in range(n - 1, -1, -1):
		c[arr[i]] -= 1
		curr -= mapp[arr[i]]
		curr += c[arr[i] + 1]
		mapp[arr[i] + 1] += 1
		ans = max(ans, curr)
	print(ans)
for t in range(int(input())):
	solve()


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	counts = (n + 1) * [0]
	processed = (n + 1) * [0]
	old = []
	for j in a:
		counts[j] += 1
	for j in range(n - 1, -1, -1):
		o = 0
		if len(old) > 0:
			o = old[-1]
		if a[j] + 1 <= n:
			new = counts[a[j] + 1] - processed[a[j] - 1] + o
		else:
			new = o - processed[a[j] - 1]
		old.append(new)
		counts[a[j]] -= 1
		processed[a[j]] += 1
	print(max(old))


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	pref = [0] * (n + 2)
	suff = [0] * (n + 2)
	for i in l:
		pref[i] += 1
	ans = 0
	count = 0
	for i in range(n - 1, -1, -1):
		count -= pref[l[i]] * suff[l[i] - 1] + pref[l[i] + 1] * suff[l[i]]
		pref[l[i]] -= 1
		suff[l[i]] += 1
		count += pref[l[i]] * suff[l[i] - 1] + pref[l[i] + 1] * suff[l[i]]
		ans = max(ans, count)
	print(ans)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	suff = [0 for i in range(n + 9)]
	pre = [0 for i in range(n + 9)]
	for i in l:
		suff[i] += 1
	(ans, res) = (0, 0)
	for i in l:
		pre[i] += 1
		suff[i] -= 1
		ans += suff[i - 1]
		ans -= pre[i + 1]
		res = max(res, ans)
	print(res)


t = int(input())
while t:
	t -= 1
	n = int(input())
	a = list(map(int, input().split()))
	prev = [0] * (n + 2)
	temp = [0] * (n + 2)
	ans = 0
	curr = 0
	for i in range(n):
		prev[a[i]] += 1
	for i in range(n - 1, -1, -1):
		curr += prev[a[i] + 1]
		curr -= temp[a[i] - 1]
		ans = max(ans, curr)
		prev[a[i]] -= 1
		temp[a[i]] += 1
	print(ans)


t = int(input())
for i in range(t):
	n = int(input())
	lst = list(map(int, input().split()))
	vec = [0] * n
	mp1 = {}
	mp2 = {}
	for j in lst:
		mp1[j] = 0
	for j in lst:
		mp1[j] += 1
	for j in lst:
		mp2[j + 1] = 0
	mp1[lst[-1]] -= 1
	if lst[-1] + 1 in mp1:
		vec[-1] = mp1[lst[-1] + 1]
	else:
		vec[-1] = 0
	mp2[lst[-1] + 1] += 1
	for j in range(n - 2, -1, -1):
		ele = lst[j]
		mp1[ele] -= 1
		if ele + 1 in mp1:
			a = mp1[ele + 1]
		else:
			a = 0
		if ele in mp2:
			b = mp2[ele]
		else:
			b = 0
		mp2[ele + 1] += 1
		ct = vec[j + 1] + a - b
		vec[j] = ct
	print(max(vec))


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	ans = 0
	d = {}
	for i in l:
		if i in d:
			d[i] += 1
		else:
			d[i] = 1
	d1 = {}
	res = 0
	for i in range(n - 1, -1, -1):
		d[l[i]] -= 1
		if l[i] + 1 in d:
			ans += d[l[i] + 1]
		if l[i] - 1 in d1:
			ans -= d1[l[i] - 1]
		if l[i] in d1:
			d1[l[i]] += 1
		else:
			d1[l[i]] = 1
		res = max(ans, res)
	print(res)


import sys
from collections import defaultdict

def solve():
	aata = int(input())
	pata = list(map(int, input().split()))
	pre = [0] * aata
	suff = [0] * aata
	zara = defaultdict(int)
	zara[pata[0]] += 1
	for i in range(1, aata):
		if pata[i] + 1 in zara:
			pre[i] = zara[pata[i] + 1]
		else:
			pre[i] = 0
		zara[pata[i]] += 1
	zara = defaultdict(int)
	zara[pata[aata - 1]] += 1
	suff[aata - 1] = 0
	for i in range(aata - 2, -1, -1):
		if pata[i] - 1 in zara:
			suff[i] = zara[pata[i] - 1]
		else:
			suff[i] = 0
		zara[pata[i]] += 1
	resta = [0] * aata
	for i in range(aata):
		resta[i] = pre[i] - suff[i]
	ansta = 0
	current = 0
	for i in range(aata - 1, -1, -1):
		current += resta[i]
		if current < 0:
			current = 0
		ansta = max(ansta, current)
	print(ansta)
ff = int(input())
for _ in range(ff):
	solve()


from collections import defaultdict

def solve():
	n = int(input())
	m = list(map(int, input().split()))
	mp1 = defaultdict(int)
	mp = defaultdict(int)
	for i in range(n):
		mp1[m[i]] += 1
	v2 = [0] * (n + 1)
	for i in range(n - 1, -1, -1):
		v2[i] = v2[i + 1] + mp1[m[i] + 1] - mp[m[i] - 1]
		mp1[m[i]] -= 1
		mp[m[i]] += 1
	r = 0
	for i in range(n):
		r = max(r, v2[i])
	print(r)
t = int(input())
for i in range(t):
	solve()


def main():
	from collections import defaultdict
	t = int(input())
	for _ in range(t):
		n = int(input())
		a = list(map(int, input().split()))
		ans = 0
		d = defaultdict(int)
		ato = defaultdict(int)
		temp = 0
		for i in range(n):
			ato[a[i]] += 1
		for i in range(n):
			temp += ato[a[i] - 1] - d[a[i] + 1]
			ans = max(ans, temp)
			d[a[i]] += 1
			ato[a[i]] -= 1
		print(ans)
main()


import sys
from collections import defaultdict

def solve():
	n = int(input())
	v = list(map(int, input().split()))
	prefix = [0] * n
	suffix = [0] * n
	mp = defaultdict(int)
	mp[v[0]] += 1
	for i in range(1, n):
		if v[i] + 1 in mp:
			prefix[i] = mp[v[i] + 1]
		else:
			prefix[i] = 0
		mp[v[i]] += 1
	mp = defaultdict(int)
	mp[v[n - 1]] += 1
	suffix[n - 1] = 0
	for i in range(n - 2, -1, -1):
		if v[i] - 1 in mp:
			suffix[i] = mp[v[i] - 1]
		else:
			suffix[i] = 0
		mp[v[i]] += 1
	res = [0] * n
	for i in range(n):
		res[i] = prefix[i] - suffix[i]
	ans = 0
	current_sum = 0
	for i in range(n - 1, -1, -1):
		current_sum += res[i]
		if current_sum < 0:
			current_sum = 0
		ans = max(ans, current_sum)
	print(ans)
t = int(input())
for _ in range(t):
	solve()


T = int(input())
y2 = int(1000000000.0 + 7)
sum = 0
p = [0] * int(1000000.0)

def fac():
	for k in range(int(1000000.0)):
		if k == 0:
			p[k] = 1
		else:
			p[k] = p[k - 1] % y2 * ((k + 1) % y2)

def pow2(a, b):
	res = 1
	while b > 0:
		if b & 1:
			res = res * a
		a = a * a
		b >>= 1
	return res

def s():
	n = int(input())
	v = list(map(int, input().split()))
	mp1 = {}
	mp = {}
	for z in range(n):
		mp1[v[z]] = mp1.get(v[z], 0) + 1
	v2 = [0] * (n + 1)
	for k in range(n - 1, -1, -1):
		v2[k] = v2[k + 1] + mp1.get(v[k] + 1, 0) - mp.get(v[k] - 1, 0)
		mp1[v[k]] -= 1
		mp[v[k]] = mp.get(v[k], 0) + 1
	a = 0
	for j in range(n):
		a = max(a, v2[j])
	print(a)
for _ in range(T):
	s()


from collections import defaultdict

def b_search(k, arr):
	(l, hi) = (0, len(arr) - 1)
	while l <= hi:
		m = (l + hi) // 2
		if arr[m] == k:
			return m
		elif arr[m] > k:
			hi = m - 1
		else:
			l = m + 1
	return l
for t in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	m = defaultdict(int)
	m1 = defaultdict(int)
	for i in a:
		m1[i] += 1
	a2 = [0 for i in range(n + 1)]
	for i in range(n - 1, -1, -1):
		a2[i] = a2[i + 1]
		a2[i] = a2[i] + m1[a[i] + 1]
		a2[i] = a2[i] - m[a[i] - 1]
		m1[a[i]] -= 1
		m[a[i]] += 1
	ans = max(a2)
	print(ans)


import math
y2 = int(1000000000.0 + 7)
sum = 0
p = [0] * int(1000000.0)

def fac():
	for i in range(int(1000000.0)):
		if i == 0:
			p[i] = 1
		else:
			p[i] = p[i - 1] % y2 * ((i + 1) % y2)

def pow2(a, b):
	res = 1
	while b > 0:
		if b & 1:
			res = res * a
		a = a * a
		b >>= 1
	return res

def solve():
	n = int(input())
	v = list(map(int, input().split()))
	mp1 = {}
	mp = {}
	for i in range(n):
		mp1[v[i]] = mp1.get(v[i], 0) + 1
	v2 = [0] * (n + 1)
	for i in range(n - 1, -1, -1):
		v2[i] = v2[i + 1] + mp1.get(v[i] + 1, 0) - mp.get(v[i] - 1, 0)
		mp1[v[i]] -= 1
		mp[v[i]] = mp.get(v[i], 0) + 1
	ans = 0
	for i in range(n):
		ans = max(ans, v2[i])
	print(ans)
t = int(input())
for _ in range(t):
	solve()


from collections import defaultdict
for _ in range(int(input())):
	N = int(input())
	A = list(map(int, input().split()))
	influence = [0] * N
	M = 0
	maxChange = 0
	d = defaultdict(lambda : list())
	d2 = defaultdict(lambda : 0)
	for i in range(N):
		d[A[i]].append(i)
	for i in range(N):
		element = A[N - 1 - i] + 1
		if element in d:
			change = len(d[element])
			M = M + change
		M = M - d2[element - 1]
		maxChange = max(M, maxChange)
		d[element - 1].pop()
		d2[element] = d2[element] + 1
		if len(d[element - 1]) == 0:
			d.pop(element - 1)
	print(maxChange)


import math

def solve():
	n = int(input())
	v = list(map(int, input().split()))
	mp1 = {}
	mp = {}
	for i in range(n):
		mp1[v[i]] = mp1.get(v[i], 0) + 1
	v2 = [0] * (n + 1)
	for i in range(n - 1, -1, -1):
		v2[i] = v2[i + 1] + mp1.get(v[i] + 1, 0) - mp.get(v[i] - 1, 0)
		mp1[v[i]] -= 1
		mp[v[i]] = mp.get(v[i], 0) + 1
	ans = 0
	for i in range(n):
		ans = max(ans, v2[i])
	print(ans)
t = int(input())
for _ in range(t):
	solve()


from collections import Counter

def read_int():
	return int(input())

def read_ints():
	return [int(x) for x in input().split()]

def read_case():
	n = read_int()
	a = read_ints()
	return (n, a)

def solve(n, a):
	pre_counts = Counter(a)
	after_counts = Counter()
	current = 0
	best = 0
	for pos in range(len(a) - 1, -1, -1):
		value = a[pos]
		pre_counts[value] -= 1
		current += pre_counts[value + 1]
		current -= after_counts[value - 1]
		after_counts[value] += 1
		best = max(best, current)
	return best
cases = read_int()
for case in range(cases):
	print(solve(*read_case()))


def solve():
	num_of_elements = int(input())
	elements = list(map(int, input().split()))
	count_dict = {}
	visited = {}
	for i in range(num_of_elements):
		count_dict[elements[i]] = count_dict.get(elements[i], 0) + 1
	reverse_count = [0] * (num_of_elements + 1)
	for i in range(num_of_elements - 1, -1, -1):
		reverse_count[i] += reverse_count[i + 1]
		reverse_count[i] += count_dict.get(elements[i] + 1, 0)
		reverse_count[i] -= visited.get(elements[i] - 1, 0)
		count_dict[elements[i]] -= 1
		visited[elements[i]] = visited.get(elements[i], 0) + 1
	max_count = 0
	for i in range(num_of_elements):
		max_count = max(max_count, reverse_count[i])
	print(max_count)
num_of_tests = int(input())
for i in range(num_of_tests):
	solve()


def minInv():
	n = int(input())
	v = list(map(int, input().split()))
	arr = {}
	arr2 = {}
	for i in v:
		arr[i] = arr.get(i, 0) + 1
	input_list = [0] * (n + 1)
	for i in range(n - 1, -1, -1):
		input_list[i] = input_list[i + 1]
		input_list[i] += arr.get(v[i] + 1, 0)
		input_list[i] -= arr2.get(v[i] - 1, 0)
		arr[v[i]] -= 1
		arr2[v[i]] = arr2.get(v[i], 0) + 1
	output = 0
	for i in range(n):
		output = max(output, input_list[i])
	print(output)
for _ in range(int(input())):
	minInv()


from collections import defaultdict
for t in range(int(input())):
	n = int(input())
	nums = list(map(int, input().split()))
	map1 = defaultdict(int)
	map2 = defaultdict(int)
	for i in nums:
		map1[i] = map1.get(i, 0) + 1
	arr = [0] * (n + 1)
	for i in range(n - 1, -1, -1):
		arr[i] = arr[i + 1]
		arr[i] = arr[i] + map1[nums[i] + 1]
		arr[i] = arr[i] - map2[nums[i] - 1]
		map1[nums[i]] -= 1
		map2[nums[i]] += 1
	ans = 0
	for i in range(n):
		ans = max(ans, arr[i])
	print(ans)


import sys

def main():
	tc = int(input())
	for _ in range(tc):
		n = int(input())
		arr = [int(a) for a in input().split()]
		if n == 1:
			print(0)
			continue
		(h, h2) = ({}, {})
		for i in range(n):
			if arr[i] not in h:
				h[arr[i]] = 0
			h[arr[i]] += 1
			h2[arr[i]] = 0
		right = [0 for i in range(n + 1)]
		for i in range(n - 1, -1, -1):
			right[i] = right[i + 1]
			if arr[i] + 1 in h:
				right[i] += h[arr[i] + 1]
			if arr[i] - 1 in h:
				right[i] -= h2[arr[i] - 1]
			h[arr[i]] -= 1
			h2[arr[i]] += 1
		ans = max(right)
		print(ans)
main()


import sys
from collections import defaultdict

def solve():
	a = int(input())
	p = list(map(int, input().split()))
	prefix = [0] * a
	suffix = [0] * a
	zk = defaultdict(int)
	zk[p[0]] += 1
	for i in range(1, a):
		if p[i] + 1 in zk:
			prefix[i] = zk[p[i] + 1]
		else:
			prefix[i] = 0
		zk[p[i]] += 1
	zk = defaultdict(int)
	zk[p[a - 1]] += 1
	suffix[a - 1] = 0
	for i in range(a - 2, -1, -1):
		if p[i] - 1 in zk:
			suffix[i] = zk[p[i] - 1]
		else:
			suffix[i] = 0
		zk[p[i]] += 1
	res = [0] * a
	for i in range(a):
		res[i] = prefix[i] - suffix[i]
	ans = 0
	current_sum = 0
	for i in range(a - 1, -1, -1):
		current_sum += res[i]
		if current_sum < 0:
			current_sum = 0
		ans = max(ans, current_sum)
	print(ans)
t = int(input())
for _ in range(t):
	solve()


import sys
from collections import defaultdict

def krdebhaiabb():
	raju = int(input())
	ramu = list(map(int, input().split()))
	neechewalipower = [0] * raju
	upperwalipower = [0] * raju
	arrrreeeee = defaultdict(int)
	arrrreeeee[ramu[0]] += 1
	for j in range(1, raju):
		if ramu[j] + 1 in arrrreeeee:
			neechewalipower[j] = arrrreeeee[ramu[j] + 1]
		else:
			neechewalipower[j] = 0
		arrrreeeee[ramu[j]] += 1
	arrrreeeee = defaultdict(int)
	arrrreeeee[ramu[raju - 1]] += 1
	upperwalipower[raju - 1] = 0
	for j in range(raju - 2, -1, -1):
		if ramu[j] - 1 in arrrreeeee:
			upperwalipower[j] = arrrreeeee[ramu[j] - 1]
		else:
			upperwalipower[j] = 0
		arrrreeeee[ramu[j]] += 1
	aaram = [0] * raju
	for j in range(raju):
		aaram[j] = neechewalipower[j] - upperwalipower[j]
	jabab = 0
	abhikaJoor = 0
	for j in range(raju - 1, -1, -1):
		abhikaJoor += aaram[j]
		if abhikaJoor < 0:
			abhikaJoor = 0
		jabab = max(jabab, abhikaJoor)
	print(jabab)
num = int(input())
for _ in range(num):
	krdebhaiabb()


import sys
from collections import defaultdict

def problem():
	naac = int(input())
	aloo = list(map(int, input().split()))
	pr = [0] * naac
	sl = [0] * naac
	Man = defaultdict(int)
	Man[aloo[0]] += 1
	for q in range(1, naac):
		if aloo[q] + 1 in Man:
			pr[q] = Man[aloo[q] + 1]
		else:
			pr[q] = 0
		Man[aloo[q]] += 1
	Man = defaultdict(int)
	Man[aloo[naac - 1]] += 1
	sl[naac - 1] = 0
	for q in range(naac - 2, -1, -1):
		if aloo[q] - 1 in Man:
			sl[q] = Man[aloo[q] - 1]
		else:
			sl[q] = 0
		Man[aloo[q]] += 1
	Riya = [0] * naac
	for n in range(naac):
		Riya[n] = pr[n] - sl[n]
	ananta = 0
	anaa = 0
	for n in range(naac - 1, -1, -1):
		anaa += Riya[n]
		if anaa < 0:
			anaa = 0
		ananta = max(ananta, anaa)
	print(ananta)
vase = int(input())
for _ in range(vase):
	problem()


import math
z2 = int(1000000000.0 + 7)
total = 0
p = [0] * int(1000000.0)

def factorial():
	for i in range(int(1000000.0)):
		if i == 0:
			p[i] = 1
		else:
			p[i] = p[i - 1] % z2 * ((i + 1) % z2)

def power2(a, b):
	result = 1
	while b > 0:
		if b & 1:
			result = result * a
		a = a * a
		b >>= 1
	return result

def solve_problem():
	n = int(input())
	v = list(map(int, input().split()))
	mp1 = {}
	mp = {}
	for i in range(n):
		mp1[v[i]] = mp1.get(v[i], 0) + 1
	v2 = [0] * (n + 1)
	for i in range(n - 1, -1, -1):
		v2[i] = v2[i + 1] + mp1.get(v[i] + 1, 0) - mp.get(v[i] - 1, 0)
		mp1[v[i]] -= 1
		mp[v[i]] = mp.get(v[i], 0) + 1
	answer = 0
	for i in range(n):
		answer = max(answer, v2[i])
	print(answer)
t = int(input())
for _ in range(t):
	solve_problem()


import collections
tc = int(input())
for _ in range(tc):
	n = int(input())
	v = list(map(int, input().split()))
	vv = [0] * (n + 1)
	mp1 = collections.Counter(v)
	mp = {}
	for i in range(n - 1, -1, -1):
		vv[i] = vv[i + 1]
		vv[i] += mp1[v[i] + 1]
		vv[i] -= mp.get(v[i] - 1, 0)
		mp1[v[i]] -= 1
		mp[v[i]] = mp.get(v[i], 0) + 1
	ans = max(vv)
	print(ans)


import math
t = int(input())
for i in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	d1 = {}
	d2 = {}
	for i in range(n):
		try:
			d1[arr[i]] += 1
		except:
			d1[arr[i]] = 1
	arr2 = [0] * (n + 1)
	for i in range(n - 1, -1, -1):
		arr2[i] = arr2[i + 1]
		try:
			arr2[i] = arr2[i] + d1[arr[i] + 1]
		except:
			pass
		try:
			arr2[i] = arr2[i] - d2[arr[i] - 1]
		except:
			pass
		try:
			d1[arr[i]] -= 1
		except:
			d1[arr[i]] = 0
		try:
			d2[arr[i]] += 1
		except:
			d2[arr[i]] = 1
	ans = 0
	for i in range(n):
		ans = max(ans, arr2[i])
	print(ans)


for _ in range(int(input())):
	n = int(input())
	arr = [int(x) for x in input().split()]
	d = {}
	cnt = [0] * n
	for i in range(n):
		cnt[i] = d.get(arr[i] + 1, 0)
		d[arr[i]] = d.get(arr[i], 0) + 1
	d = {}
	for i in range(n - 1, -1, -1):
		if i + 1 < n:
			cnt[i] += cnt[i + 1]
		cnt[i] -= d.get(arr[i] - 1, 0)
		d[arr[i]] = d.get(arr[i], 0) + 1
	print(max(cnt))


import sys
from collections import defaultdict

def idjjd():
	iva = 7
	dkd = int(input())
	dwkok = list(map(int, input().split()))
	wokfwf = [0] * dkd
	abh = 4
	smnmnjf = [0] * dkd
	fnvnvj = defaultdict(int)
	konde = 2
	fnvnvj[dwkok[0]] += 1
	sur = 1
	for f in range(10):
		for t in range(4):
			if konde > abh:
				abh += 2
				break
	for i in range(1, dkd):
		if dwkok[i] + 1 in fnvnvj:
			wokfwf[i] = fnvnvj[dwkok[i] + 1]
		else:
			wokfwf[i] = 0
		fnvnvj[dwkok[i]] += 1
	for l in range(3):
		for w in range(5):
			if sur > konde:
				sur += 3
				break
	fnvnvj = defaultdict(int)
	fnvnvj[dwkok[dkd - 1]] += 1
	smnmnjf[dkd - 1] = 0
	while sur == 100:
		for d in range(15):
			for s in range(10):
				if sur > abh:
					sur += 2
					break
	for i in range(dkd - 2, -1, -1):
		if dwkok[i] - 1 in fnvnvj:
			smnmnjf[i] = fnvnvj[dwkok[i] - 1]
		else:
			smnmnjf[i] = 0
		fnvnvj[dwkok[i]] += 1
	mjdj = [0] * dkd
	for i in range(dkd):
		mjdj[i] = wokfwf[i] - smnmnjf[i]
	cnnfj = 0
	snnkfifeio = 0
	for e in range(20):
		if abh == 9:
			abh += konde
			break
	for i in range(dkd - 1, -1, -1):
		snnkfifeio += mjdj[i]
		if snnkfifeio < 0:
			snnkfifeio = 0
		cnnfj = max(cnnfj, snnkfifeio)
	while abh > iva:
		for g in range(6):
			for s in range(2):
				if iva == 40:
					iva += abh
					break
	print(cnnfj)
for _ in range(int(input())):
	idjjd()


y = 1000000000.0 + 7
sum = 0
yo = [0] * int(1000000.0)

def fun1():
	for i in range(int(1000000.0)):
		if i == 0:
			yo[i] = 1
		else:
			yo[i] = yo[i - 1] % y * ((i + 1) % y)

def fun2(a, b):
	res = 1
	while b > 0:
		if b & 1:
			res = res * a
		a = a * a
		b >>= 1
	return res

def main():
	n = int(input())
	m = [int(x) for x in input().split()]
	o = {}
	p = {}
	for i in range(n):
		o[m[i]] = o.get(m[i], 0) + 1
	q = [0] * (n + 1)
	for i in range(n - 1, -1, -1):
		q[i] = q[i + 1] + o.get(m[i] + 1, 0) - p.get(m[i] - 1, 0)
		o[m[i]] = o.get(m[i], 0) - 1
		p[m[i]] = p.get(m[i], 0) + 1
	ans = 0
	for i in range(n):
		ans = max(ans, q[i])
	print(ans)
for _ in range(int(input())):
	main()
	print()


import sys
from collections import defaultdict

def answer():
	Nitya = int(input())
	alue = list(map(int, input().split()))
	process = [0] * Nitya
	sol = [0] * Nitya
	Mum = defaultdict(int)
	Mum[alue[0]] += 1
	for l in range(1, Nitya):
		if alue[l] + 1 in Mum:
			process[l] = Mum[alue[l] + 1]
		else:
			process[l] = 0
		Mum[alue[l]] += 1
	Mum = defaultdict(int)
	Mum[alue[Nitya - 1]] += 1
	sol[Nitya - 1] = 0
	for m in range(Nitya - 2, -1, -1):
		if alue[m] - 1 in Mum:
			sol[m] = Mum[alue[m] - 1]
		else:
			sol[m] = 0
		Mum[alue[m]] += 1
	Rhi = [0] * Nitya
	for m in range(Nitya):
		Rhi[m] = process[m] - sol[m]
	samarth = 0
	chotu = 0
	for m in range(Nitya - 1, -1, -1):
		chotu += Rhi[m]
		if chotu < 0:
			chotu = 0
		samarth = max(samarth, chotu)
	print(samarth)
casanova = int(input())
for _ in range(casanova):
	answer()


import sys
from collections import defaultdict

def soltion():
	n = int(input())
	v = list(map(int, input().split()))
	prefix = [0] * n
	suffix = [0] * n
	arr = defaultdict(int)
	arr[v[0]] += 1
	for i in range(1, n):
		if v[i] + 1 in arr:
			prefix[i] = arr[v[i] + 1]
		else:
			prefix[i] = 0
		arr[v[i]] += 1
	arr = defaultdict(int)
	arr[v[n - 1]] += 1
	suffix[n - 1] = 0
	for i in range(n - 2, -1, -1):
		if v[i] - 1 in arr:
			suffix[i] = arr[v[i] - 1]
		else:
			suffix[i] = 0
		arr[v[i]] += 1
	res = [0] * n
	for i in range(n):
		res[i] = prefix[i] - suffix[i]
	ans = 0
	sum = 0
	for i in range(n - 1, -1, -1):
		sum += res[i]
		if sum < 0:
			sum = 0
		ans = max(ans, sum)
	print(ans)
t = int(input())
for _ in range(t):
	soltion()


import sys
from collections import defaultdict

def solve():
	pehla = int(input())
	dusra = list(map(int, input().split()))
	tessra = [0] * pehla
	chautha = [0] * pehla
	popo = defaultdict(int)
	popo[dusra[0]] += 1
	for f in range(1, pehla):
		if dusra[f] + 1 in popo:
			tessra[f] = popo[dusra[f] + 1]
		else:
			tessra[f] = 0
		popo[dusra[f]] += 1
	popo = defaultdict(int)
	popo[dusra[pehla - 1]] += 1
	chautha[pehla - 1] = 0
	for f in range(pehla - 2, -1, -1):
		if dusra[f] - 1 in popo:
			chautha[f] = popo[dusra[f] - 1]
		else:
			chautha[f] = 0
		popo[dusra[f]] += 1
	res = [0] * pehla
	for f in range(pehla):
		res[f] = tessra[f] - chautha[f]
	hell = 0
	turnt = 0
	for f in range(pehla - 1, -1, -1):
		turnt += res[f]
		if turnt < 0:
			turnt = 0
		hell = max(hell, turnt)
	print(hell)
t = int(input())
for _ in range(t):
	solve()


import math
import sys
from collections import Counter

def find_good_arrays(A):
	N = len(A)
	B = []
	C = []
	D = []
	result = 0
	for i in range(N):
		if is_valid(B, C, D, A[i]):
			B.append(A[i])
			update_c_and_d(C, D, A[i])
		else:
			result += len(B)
			B = [A[i]]
			C = []
			D = []
			update_c_and_d(C, D, A[i])
	result += len(B)
	return result % 10 ** 7

def is_valid(B, C, D, x):
	if len(C) == 0:
		return True
	if C[-1] == 0:
		return False
	if C[-1] * (C[-1] - x) >= 0:
		return False
	if Counter(bin(D[-1]))['1'] % 2 == 0:
		return False
	return True

def update_c_and_d(C, D, x):
	if len(B) > 1:
		C.append(B[-1] - B[-2])
		D.append(B[-1] | B[-2])

def samasya_solving():
	edo = int(input())
	modhatidhi = [int(x) for x in input().split()]
	ento_idi = {}
	idento_mari = {}
	for i in range(edo):
		modhatidhi[i]
		ento_idi[modhatidhi[i]] = ento_idi.get(modhatidhi[i], 0) + 1
	anthey_neney = [0] * (edo + 1)
	for i in range(edo - 1, -1, -1):
		anthey_neney[i] = anthey_neney[i + 1]
		anthey_neney[i] = anthey_neney[i] + ento_idi.get(modhatidhi[i] + 1, 0)
		anthey_neney[i] = anthey_neney[i] - idento_mari.get(modhatidhi[i] - 1, 0)
		ento_idi[modhatidhi[i]] = ento_idi.get(modhatidhi[i], 0) - 1
		idento_mari[modhatidhi[i]] = idento_mari.get(modhatidhi[i], 0) + 1
	sol = 0
	for i in range(edo):
		sol = max(sol, anthey_neney[i])
	print(sol)
t = int(input())
while t > 0:
	t -= 1
	samasya_solving()


def solve():
	n = int(input())
	v = [int(x) for x in input().split()]
	mp1 = {}
	mp = {}
	for i in range(n):
		mp1[v[i]] = mp1.get(v[i], 0) + 1
	v2 = [0] * (n + 1)
	for i in range(n - 1, -1, -1):
		v2[i] = v2[i + 1] + mp1.get(v[i] + 1, 0) - mp.get(v[i] - 1, 0)
		mp1[v[i]] -= 1
		mp[v[i]] = mp.get(v[i], 0) + 1
	ans = max(v2)
	print(ans)
t = int(input())
for i in range(t):
	solve()


def solve():
	num_of_tests = int(input())
	arr = [int(x) for x in input().split()]
	num_count = {}
	inversions = {}
	for i in range(num_of_tests):
		num_count[arr[i]] = num_count.get(arr[i], 0) + 1
	inverted_nums = [0] * (num_of_tests + 1)
	for i in range(num_of_tests - 1, -1, -1):
		inverted_nums[i] = inverted_nums[i + 1] + num_count.get(arr[i] + 1, 0) - inversions.get(arr[i] - 1, 0)
		num_count[arr[i]] = num_count.get(arr[i], 0) - 1
		inversions[arr[i]] = inversions.get(arr[i], 0) + 1
	max_inversions = 0
	for i in range(num_of_tests):
		max_inversions = max(max_inversions, inverted_nums[i])
	print(max_inversions)
num_of_cases = int(input())
for _ in range(num_of_cases):
	solve()


from collections import defaultdict
m = int(input())
for i in range(m):
	n = int(input())
	a = list(map(int, input().split()))
	x = [0] * n
	y = [0] * n
	q = defaultdict(int)
	q[a[0]] += 1
	for j in range(1, n):
		if a[j] + 1 in q:
			x[j] = q[a[j] + 1]
		else:
			x[j] = 0
		q[a[j]] += 1
	q = defaultdict(int)
	q[a[n - 1]] += 1
	y[n - 1] = 0
	for k in range(n - 2, -1, -1):
		if a[k] - 1 in q:
			y[k] = q[a[k] - 1]
		else:
			y[k] = 0
		q[a[k]] += 1
	r = [0] * n
	for w in range(n):
		r[w] = x[w] - y[w]
	s = 0
	ns = 0
	for e in range(n - 1, -1, -1):
		ns += r[e]
		if ns < 0:
			ns = 0
		s = max(s, ns)
	print(s)


import sys, threading
import math
from os import path
from collections import deque, defaultdict, Counter
from bisect import *
from string import ascii_lowercase
from functools import cmp_to_key
from random import randint
import heapq

def readInts():
	x = list(map(int, sys.stdin.readline().rstrip().split()))
	return x[0] if len(x) == 1 else x

def readList(type=int):
	x = sys.stdin.readline()
	x = list(map(type, x.rstrip('\n\r').split()))
	return x

def readStr():
	x = sys.stdin.readline().rstrip('\r\n')
	return x
write = sys.stdout.write
read = sys.stdin.readline
MAXN = 1123456

class mydict:

	def __init__(self, func=lambda : 0):
		self.random = randint(0, 1 << 32)
		self.default = func
		self.dict = {}

	def __getitem__(self, key):
		mykey = self.random ^ key
		if mykey not in self.dict:
			self.dict[mykey] = self.default()
		return self.dict[mykey]

	def get(self, key, default):
		mykey = self.random ^ key
		if mykey not in self.dict:
			return default
		return self.dict[mykey]

	def __setitem__(self, key, item):
		mykey = self.random ^ key
		self.dict[mykey] = item

	def getkeys(self):
		return [self.random ^ i for i in self.dict]

	def __str__(self):
		return f'{[(self.random ^ i, self.dict[i]) for i in self.dict]}'

def lcm(a, b):
	return a * b // math.gcd(a, b)

def mod(n):
	return n % 1000000007

def solve(t):
	n = readInts()
	ar = readList()
	mp = Counter(ar)
	prev = set()
	ans = float('-inf')
	cur = 0
	left = mydict(lambda : 0)
	for i in range(n):
		cur -= left[ar[i] + 1]
		cur += mp[ar[i] - 1]
		prev.add(ar[i])
		left[ar[i]] += 1
		mp[ar[i]] -= 1
		ans = max(ans, cur)
	print(ans)

def main():
	t = 1
	if path.exists('F:/Comp Programming/input.txt'):
		sys.stdin = open('F:/Comp Programming/input.txt', 'r')
		sys.stdout = open('F:/Comp Programming/output1.txt', 'w')
	t = readInts()
	for i in range(t):
		solve(i + 1)
main()


import sys
from collections import defaultdict

def vikasfun():
	vikas_num = int(input())
	vikas_list = list(map(int, input().split()))
	vikasprefix = [0] * vikas_num
	vikassuffix = [0] * vikas_num
	vikas_mp = defaultdict(int)
	vikas_mp[vikas_list[0]] += 1
	for vikas in range(1, vikas_num):
		if vikas_list[vikas] + 1 in vikas_mp:
			vikasprefix[vikas] = vikas_mp[vikas_list[vikas] + 1]
		else:
			vikasprefix[vikas] = 0
		vikas_mp[vikas_list[vikas]] += 1
	vikas_mp = defaultdict(int)
	vikas_mp[vikas_list[vikas_num - 1]] += 1
	vikassuffix[vikas_num - 1] = 0
	for vikas in range(vikas_num - 2, -1, -1):
		if vikas_list[vikas] - 1 in vikas_mp:
			vikassuffix[vikas] = vikas_mp[vikas_list[vikas] - 1]
		else:
			vikassuffix[vikas] = 0
		vikas_mp[vikas_list[vikas]] += 1
	vikasres = [0] * vikas_num
	for vikas in range(vikas_num):
		vikasres[vikas] = vikasprefix[vikas] - vikassuffix[vikas]
	vikasans = 0
	vikassum = 0
	for vikas in range(vikas_num - 1, -1, -1):
		vikassum += vikasres[vikas]
		if vikassum < 0:
			vikassum = 0
		vikasans = max(vikasans, vikassum)
	print(vikasans)
vikastest = int(input())
for x in range(vikastest):
	vikasfun()


import sys
from collections import defaultdict

def solve():
	newvar = int(input())
	second = list(map(int, input().split()))
	precode = [0] * newvar
	postcode = [0] * newvar
	mp = defaultdict(int)
	mp[second[0]] += 1
	for i in range(1, newvar):
		if second[i] + 1 in mp:
			precode[i] = mp[second[i] + 1]
		else:
			precode[i] = 0
		mp[second[i]] += 1
	mp = defaultdict(int)
	mp[second[newvar - 1]] += 1
	postcode[newvar - 1] = 0
	for i in range(newvar - 2, -1, -1):
		if second[i] - 1 in mp:
			postcode[i] = mp[second[i] - 1]
		else:
			postcode[i] = 0
		mp[second[i]] += 1
	res = [0] * newvar
	for i in range(newvar):
		res[i] = precode[i] - postcode[i]
	ans = 0
	sumofcode = 0
	for i in range(newvar - 1, -1, -1):
		sumofcode += res[i]
		if sumofcode < 0:
			sumofcode = 0
		ans = max(ans, sumofcode)
	print(ans)
t = int(input())
for _ in range(t):
	solve()


from collections import defaultdict
ff = 1000000000.0 + 7
sum = 0

def fac():
	for i in range(10 ** 6):
		if i == 0:
			p[i] = 1
		else:
			p[i] = p[i - 1] % ff * ((i + 1) % ff)

def pow2(a, b):
	res = 1
	while b:
		if b & 1:
			res *= a
		a *= a
		b >>= 1
	return res
t = 1
t = int(input())
while t:
	n = int(input())
	lis = list(map(int, input().split()))
	map0 = defaultdict(int)
	map1 = defaultdict(int)
	for i in range(n):
		if lis[i] in map0:
			map0[lis[i]] += 1
		else:
			map0[lis[i]] = 1
	lis2 = [0] * (n + 1)
	for i in range(n - 1, -1, -1):
		lis2[i] = lis2[i + 1]
		lis2[i] += map0[lis[i] + 1]
		lis2[i] -= map1[lis[i] - 1]
		map0[lis[i]] -= 1
		map1[lis[i]] += 1
	ans = max(lis2)
	print(ans)
	t -= 1


import sys
from collections import defaultdict

def answerfind():
	rish = int(input())
	abh = list(map(int, input().split()))
	prefix = [0] * rish
	suffix = [0] * rish
	mpmla = defaultdict(int)
	mpmla[abh[0]] += 1
	for i in range(1, rish):
		if abh[i] + 1 in mpmla:
			prefix[i] = mpmla[abh[i] + 1]
		else:
			prefix[i] = 0
		mpmla[abh[i]] += 1
	mpmla = defaultdict(int)
	mpmla[abh[rish - 1]] += 1
	suffix[rish - 1] = 0
	for i in range(rish - 2, -1, -1):
		if abh[i] - 1 in mpmla:
			suffix[i] = mpmla[abh[i] - 1]
		else:
			suffix[i] = 0
		mpmla[abh[i]] += 1
	res = [0] * rish
	for i in range(rish):
		res[i] = prefix[i] - suffix[i]
	answithrish = 0
	currwithrish = 0
	for i in range(rish - 1, -1, -1):
		currwithrish += res[i]
		if currwithrish < 0:
			currwithrish = 0
		answithrish = max(answithrish, currwithrish)
	print(answithrish)
t = int(input())
for _ in range(t):
	answerfind()


import sys
from collections import defaultdict

def mona():
	m = int(input())
	s = list(map(int, input().split()))
	prefix = [0] * m
	suffix = [0] * m
	mp = defaultdict(int)
	mp[s[0]] += 1
	for i in range(1, m):
		if s[i] + 1 in mp:
			prefix[i] = mp[s[i] + 1]
		else:
			prefix[i] = 0
		mp[s[i]] += 1
	mp = defaultdict(int)
	mp[s[m - 1]] += 1
	suffix[m - 1] = 0
	for i in range(m - 2, -1, -1):
		if s[i] - 1 in mp:
			suffix[i] = mp[s[i] - 1]
		else:
			suffix[i] = 0
		mp[s[i]] += 1
	res = [0] * m
	for i in range(m):
		res[i] = prefix[i] - suffix[i]
	ans = 0
	current_sum = 0
	for i in range(m - 1, -1, -1):
		current_sum += res[i]
		if current_sum < 0:
			current_sum = 0
		ans = max(ans, current_sum)
	print(ans)
p = int(input())
for _ in range(p):
	mona()


from functools import lru_cache
import atexit, io
import sys
from math import log2
import math
from heapq import heappush, heappop, heapify
from bisect import bisect_left, bisect_right, insort
from math import gcd
from math import sqrt
from collections import Counter, defaultdict
from heapq import heappush, heappop, heapify

class FenvickTree:

	def __init__(self, n):
		self.farr = [0] * (n + 1)

	def prefixSum(self, idx):
		s = 0
		while idx > 0:
			s += self.farr[idx]
			idx -= idx & -idx
		return s

	def update(self, idx, val):
		while idx < len(self.farr):
			self.farr[idx] += val
			idx += idx & -idx

class FenvTree:

	def __init__(self, arr):
		arr.insert(0, 0)
		self.farr = [0]
		prefix = [0]
		for i in arr[1:]:
			prefix.append(prefix[-1] + i)
		for i in range(1, len(arr)):
			idash = i - (i & -i)
			self.farr.append(prefix[i] - prefix[idash])

	def query(self, l, r):
		return self.prefixSum(r) - self.prefixSum(l - 1)

	def prefixSum(self, idx):
		s = 0
		while idx > 0:
			s += self.farr[idx]
			idx -= idx & -idx
		return s

	def update(self, idx, val):
		while idx < len(self.farr):
			self.farr[idx] += val
			idx += idx & -idx

class DSU:

	def __init__(self, n):
		self.parent = []
		self.size = []
		for i in range(n + 1):
			self.parent.append(i)
			self.size.append(1)

	def union(self, u, v):
		pu = self.findPar(u)
		pv = self.findPar(v)
		if pu == pv:
			return
		if self.size[pu] < self.size[pv]:
			self.parent[pu] = pv
			self.size[pv] += self.size[pu]
		else:
			self.parent[pv] = pu
			self.size[pu] += self.size[pv]

	def unionByRank(self, u, v):
		pu = self.findPar(u)
		pv = self.findPar(v)
		if pu == pv:
			return
		if self.rank[pu] < self.rank[pv]:
			self.parent[pu] = pv
		elif self.rank[pv] < self.rank[pu]:
			self.parent[pv] = pu
		else:
			self.parent[pu] = pv
			self.rank[pv] += 1

	def findPar(self, node):
		if self.parent[node] == node:
			return node
		self.parent[node] = self.findPar(self.parent[node])
		return self.parent[node]

class info:

	def __init__(self, _open=0, _close=0, _full=0):
		self.open = _open
		self.close = _close
		self.full = _full

class SGTree:

	def __init__(self, n):
		self.seg = [0 for _ in range(4 * n)]

	def build(self, ind, low, high, arr):
		if low == high:
			self.seg[ind] = arr[low]
			return
		mid = (low + high) // 2
		self.build(2 * ind + 1, low, mid, arr)
		self.build(2 * ind + 2, mid + 1, high, arr)
		self.seg[ind] = min(self.seg[2 * ind + 1], self.seg[2 * ind + 2])

	def query(self, ind, low, high, l, r):
		if r < low or l > high:
			return sys.maxsize
		if low <= l and r >= high:
			return self.seg[ind]
		mid = low + high >> 1
		left = self.query(2 * ind + 1, 0, mid, l, r)
		right = self.query(2 * ind + 2, mid + 1, high, l, r)
		return min(left, right)

	def update(self, ind, low, high, i, val):
		if low == high:
			self.seg = val
			return
		mid = low + high >> 1
		if i <= mid:
			self.update(2 * ind + 1, low, mid, i, val)
		else:
			self.update(2 * ind + 1, mid + 1, high, i, val)
		self.seg[ind] = min(self.seg[2 * ind + 1], self.seg[2 * ind + 2])

def isPalindrome(s):
	i = 0
	j = len(s) - 1
	while i < j:
		if s[i] != s[j]:
			return False
		i += 1
		j -= 1
	return True

def IntList():
	return list(map(int, sys.stdin.readline().strip().split()))

def getInts():
	return map(int, sys.stdin.readline().strip().split())

def getStrs():
	return sys.stdin.readline().strip()

def StrList():
	list(sys.stdin.readline().strip())

def FloatList():
	lis = input().split()
	lis = list(map(float, lis))
	return lis

def SieveOfEratosthenes(n, isPrime):
	isPrime[0] = isPrime[1] = False
	for i in range(2, n + 1):
		isPrime[i] = True
	p = 2
	while p * p <= n:
		if isPrime[p]:
			i = p * p
			while i <= n:
				isPrime[i] = False
				i += p
		p += 1

def findPrimePair(n):
	isPrime = [0] * (n + 1)
	SieveOfEratosthenes(n, isPrime)
	for i in range(0, n):
		if isPrime[i] and isPrime[n - i]:
			print(i, n - i)
			return

def query(ind, low, high, l, r, seg):
	if r < low or l > high:
		return info()
	if low <= l and r >= high:
		return self.seg[ind]
	mid = low + high >> 1
	left = self.query(2 * ind + 1, 0, mid, l, r, seg)
	right = self.query(2 * ind + 2, mid + 1, high, l, r, seg)
	return merge(left, right)

def merge(left, right):
	ans = info()
	ans.full = left.full + right.full + min(left.open, right.close)
	ans.open = left.open + right.open + min(left.open, right.close)
	ans.close = left.close + right.close + min(left.open, right.close)
	return ans

def build(ind, low, high, s, seg):
	if low == high:
		seg[ind] = info(s[low] == '(', s[low] == ')', 0)
		return
	mid = (low + high) // 2
	build(2 * ind + 1, low, mid, s, seg)
	build(2 * ind + 2, mid + 1, high, s, seg)
	seg[ind] = merge(seg[2 * ind + 1], seg[2 * ind + 2])

def countN(lis):
	ans = 0
	cnt = 0
	for i in range(len(lis) - 1, -1, -1):
		if lis[i] == 0:
			cnt += 1
		else:
			ans += cnt
	return ans

class Pair:

	def __init__(self, x, y, gcd):
		self.x = x
		self.y = y
		self.gcd = gcd

def Euclidean(a, b):
	if b == 0:
		return Pair(1, 0, a)
	dash = Euclidean(b, a % b)
	return Pair(dash.y, dash.x - a // b * dash.y, dash.gcd)

def chineseRemainder(a1, n1, a2, n2):
	p = Euclidean(n1, n2)
	x = p.x
	gcd = p.gcd
	if (a1 - a2) % gcd:
		return -1
	k = (a1 - a2) // gcd
	a = a1 - n1 * (k * x % n2 // gcd)
	lcm = n1 * n2 // gcd
	if a < 0:
		a += lcm
	return a

def ncr(n, k, md):
	mod = 998244353
	tab = [[0 for _ in range(k + 1)] for i in range(n + 1)]
	for i in range(1, len(tab)):
		tab[i][0] = 1
	for i in range(1, len(tab)):
		for j in range(1, min(i + 1, len(tab[0]))):
			if i == 1 and j == 1:
				tab[i][j] = 1
			else:
				tab[i][j] = (tab[i - 1][j] + tab[i - 1][j - 1]) % mod
	return tab

def repeat(i, j, arr):
	if i > j:
		return
	cnt1 = i
	cnt2 = j
	while cnt1 < cnt2:
		(arr[cnt1], arr[cnt2]) = (arr[cnt2], arr[cnt1])
		cnt1 += 1
		cnt2 -= 1
	if i - 1 >= 0:
		ele = arr[i - 1]
		if ele > 0:
			s = int(sqrt(ele - 1)) + 1
			first = s * s - ele
			repeat(first, i - 1, arr)
	return
spf = []

def makeSeive(n):
	for i in range(n + 1):
		spf.append(i)

def seive(n):
	s = int(sqrt(n + 1))
	for i in range(2, s + 1):
		if spf[i] == i:
			for j in range(i * i, n + 1, i):
				if spf[j] == j:
					spf[j] = i

def getFactorization(x):
	ret = []
	while x != 1:
		ret.append(spf[x])
		x = x // spf[x]
	return list(set(ret))

def getLPS(s):
	st = '@#' + '#'.join(s) + '#&'
	c = 0
	r = 0
	lps = [0] * len(st)
	for i in range(1, len(st) - 1):
		mirror = c - (i - c)
		if i < r and mirror >= 0:
			lps[i] = min(lps[mirror], r - i)
		while st[i + lps[i] + 1] == st[i - lps[i] - 1]:
			lps[i] += 1
		if i + lps[i] > r:
			r = i + lps[i]
			c = i
	return max(lps)
fact = [1]
mod = 10 ** 9 + 7

def getFact(n):
	for i in range(1, n + 1):
		fact.append(i * fact[-1] % mod)

def getInv(word):
	num = math.factorial(len(word))
	for v in Counter(word).values():
		num = num * pow(math.factorial(v), mod - 2, mod) % mod
	return int(num) % (10 ** 9 + 7)

def subarrayXor(arr, n, m):
	HashTable = defaultdict(bool)
	HashTable[0] = 1
	count = 0
	curSum = 0
	for i in arr:
		curSum ^= i
		if HashTable[curSum ^ m]:
			count += HashTable[curSum ^ m]
		HashTable[curSum] += 1
	return count

def get2dPrefixSum(matrix, mid=0):
	n = len(matrix)
	m = len(matrix[0])
	prefix = [[0 for _ in range(m + 1)] for i in range(n + 1)]
	for i in range(1, n + 1):
		for j in range(1, m + 1):
			prefix[i][j] = prefix[i - 1][j] + prefix[i][j - 1] - prefix[i - 1][j - 1] + matrix[i - 1][j - 1]
	return prefix

def get2dPrefixSumCnt(matrix, mid=0):
	n = len(matrix)
	m = len(matrix[0])
	prefix = [[0 for _ in range(m + 1)] for i in range(n + 1)]
	for i in range(1, n + 1):
		for j in range(1, m + 1):
			prefix[i][j] = prefix[i - 1][j] + prefix[i][j - 1] - prefix[i - 1][j - 1] + matrix[i - 1][j - 1]
	return prefix

def getSumRange(r1, c1, r2, c2, prefix):
	cnt = prefix[r2][c2] - prefix[r2][c1 - 1] - prefix[r1 - 1][c2] + prefix[r1 - 1][c1 - 1]
	return cnt

def getPrefix(arr):
	prefix = [0]
	for i in arr:
		prefix.append(prefix[-1] + i)
	return prefix

def getInv(arr):
	cnt = 0
	ans = []
	for i in arr:
		ind = bisect_right(ans, i)
		cnt += len(ans) - ind
		insort(ans, i)
	return cnt

def solveFor():
	n = int(input())
	lis = IntList()
	c = Counter(lis)
	c1 = Counter()
	v2 = [0] * (n + 1)
	for i in range(n - 1, -1, -1):
		v2[i] = v2[i + 1]
		v2[i] = v2[i] + c[lis[i] + 1]
		v2[i] = v2[i] - c1[lis[i] - 1]
		c[lis[i]] -= 1
		c1[lis[i]] += 1
	ans = 0
	for i in range(n):
		ans = max(ans, v2[i])
	print(ans)
t = 1
t = int(input())
for i in range(t):
	solveFor()


t = int(input())
for i in range(t):
	n = int(input())
	v = list(map(int, input().split()))
	second = {}
	p = {}
	for i in v:
		if i in second:
			second[i] += 1
		else:
			second[i] = 1
	v2 = [0] * (n + 1)
	for i in range(n - 1, -1, -1):
		v2[i] = v2[i + 1]
		v2[i] += second.get(v[i] + 1, 0)
		v2[i] -= p.get(v[i] - 1, 0)
		second[v[i]] -= 1
		if v[i] in p:
			p[v[i]] += 1
		else:
			p[v[i]] = 1
	ans = 0
	for i in v2:
		ans = max(ans, i)
	print(ans)


import sys
from collections import defaultdict

def solution():
	N = int(input())
	Val = list(map(int, input().split()))
	P = [0] * N
	S = [0] * N
	M = defaultdict(int)
	M[Val[0]] += 1
	for j in range(1, N):
		if Val[j] + 1 in M:
			P[j] = M[Val[j] + 1]
		else:
			P[j] = 0
		M[Val[j]] += 1
	M = defaultdict(int)
	M[Val[N - 1]] += 1
	S[N - 1] = 0
	for k in range(N - 2, -1, -1):
		if Val[k] - 1 in M:
			S[k] = M[Val[k] - 1]
		else:
			S[k] = 0
		M[Val[k]] += 1
	R = [0] * N
	for j in range(N):
		R[j] = P[j] - S[j]
	aastha = 0
	chini = 0
	for j in range(N - 1, -1, -1):
		chini += R[j]
		if chini < 0:
			chini = 0
		aastha = max(aastha, chini)
	print(aastha)
caes = int(input())
for _ in range(caes):
	solution()


from collections import defaultdict
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split(' ')))
	mpdef1 = defaultdict(int)
	mpdef = defaultdict(int)
	for i in range(n):
		mpdef1[arr[i]] += 1
	nums = [0] * (n + 1)
	for i in range(n - 1, -1, -1):
		nums[i] += nums[i + 1]
		nums[i] += mpdef1[arr[i] + 1]
		nums[i] -= mpdef[arr[i] - 1]
		mpdef1[arr[i]] -= 1
		mpdef[arr[i]] += 1
	ans = 0
	for i in range(n):
		ans = max(ans, nums[i])
	print(ans)


from collections import defaultdict

def N():
	return int(input())

def A():
	return [int(x) for x in input().split()]

def S():
	return input()

def merge(v, ans, l, mid, h):
	t = []
	i = l
	j = mid + 1
	while i < mid + 1 and j <= h:
		if v[i][0] > v[j][0]:
			ans[v[i][1]] += h - j + 1
			t.append(v[i])
			i += 1
		else:
			t.append(v[j])
			j += 1
	while i <= mid:
		t.append(v[i])
		i += 1
	while j <= h:
		t.append(v[j])
		j += 1
	k = 0
	i = l
	while i <= h:
		v[i] = t[k]
		i += 1
		k += 1

def mergesort(v, ans, i, j):
	if i < j:
		mid = (i + j) // 2
		mergesort(v, ans, i, mid)
		mergesort(v, ans, mid + 1, j)
		merge(v, ans, i, mid, j)

def constructLowerArray(arr, n):
	v = []
	for i in range(n):
		v.append([arr[i], i])
	ans = [0] * n
	mergesort(v, ans, 0, n - 1)
	return (ans, sum(ans))

def factors(n: int) -> list:
	s = set()
	step = 2 if n % 2 else 1
	for i in range(1, n ** 0.5 + 1, step):
		if n % i == 0:
			s.add(i)
			s.add(n // i)
	return factors
for _ in range(N()):
	n = N()
	dp = [0 for i in range(n + 1)]
	if 'codechef' == 28226329:
		print('Tanmay')
	d1 = defaultdict(int)
	a = A()
	d2 = defaultdict(int)
	for i in a:
		d1[i] += 1
	for i in range(n - 1, -1, -1):
		dp[i] = dp[i + 1] - d2[a[i] - 1] + d1[1 + a[i]]
		d2[a[i]] += 1
		d1[a[i]] -= 1
	print(max(dp))


from collections import Counter
for j in range(int(input())):
	x = int(input())
	val = list(map(int, input().split()))
	mp_1 = Counter(val)
	m = {}
	v_2 = [0] * (x + 1)
	for i in range(x - 1, -1, -1):
		v_2[i] += v_2[i + 1]
		v_2[i] += mp_1[val[i] + 1]
		v_2[i] -= m.get(val[i] - 1, 0)
		mp_1[val[i]] -= 1
		m[val[i]] = m.get(val[i], 0) + 1
	answer = 0
	for i in range(x):
		answer = max(answer, v_2[i])
	print(answer)


def apple():
	banana = int(input())
	orange = list(map(int, input().split()))
	mercedes = {}
	porsche = {}
	for europe in range(banana):
		mercedes[orange[europe]] = mercedes.get(orange[europe], 0) + 1
	ford = [0] * (banana + 1)
	for europe in range(banana - 1, -1, -1):
		ford[europe] = ford[europe + 1] + mercedes.get(orange[europe] + 1, 0) - porsche.get(orange[europe] - 1, 0)
		mercedes[orange[europe]] -= 1
		porsche[orange[europe]] = porsche.get(orange[europe], 0) + 1
	microsoft = 0
	for europe in range(banana):
		microsoft = max(microsoft, ford[europe])
	print(microsoft)
apple_count = int(input())
for i in range(apple_count):
	apple()


def ans(arr):
	plus = []
	for i in arr:
		plus.append(0)
	mp = {}
	for ii in range(len(arr)):
		i = arr[ii]
		if i in mp:
			mp[i] += 1
		else:
			mp[i] = 1
		if i + 1 in mp:
			plus[ii] = mp[i + 1]
	j = 0
	i = 0
	ans = 0
	temp = 0
	c = {}
	while j < len(arr):
		if temp <= 0:
			while i < j:
				temp -= plus[i]
				if arr[i] - 1 in c:
					temp += c[arr[i] - 1]
				c[arr[i]] -= 1
				ans = max(temp, ans)
				i += 1
			temp = 0
			c = {}
		temp += plus[j]
		if arr[j] + 1 in c:
			temp -= c[arr[j] + 1]
		if arr[j] in c:
			c[arr[j]] += 1
		else:
			c[arr[j]] = 1
		ans = max(temp, ans)
		j += 1
	while i < j:
		temp -= plus[i]
		if arr[i] - 1 in c:
			temp += c[arr[i] - 1]
		c[arr[i]] -= 1
		ans = max(temp, ans)
		i += 1
	return ans
for _ in range(int(input())):
	input()
	print(ans(list(map(int, input().split()))))


t = int(input())
for _ in range(t):
	num_of_elements = int(input())
	array = list(map(int, input().split()))
	frequency_map1 = {}
	frequency_map2 = {}
	for i in range(num_of_elements):
		frequency_map1[array[i]] = frequency_map1.get(array[i], 0) + 1
	result_array = [0] * (num_of_elements + 1)
	for i in range(num_of_elements - 1, -1, -1):
		result_array[i] = result_array[i + 1]
		result_array[i] += frequency_map1.get(array[i] + 1, 0)
		result_array[i] -= frequency_map2.get(array[i] - 1, 0)
		frequency_map1[array[i]] = frequency_map1.get(array[i], 0) - 1
		frequency_map2[array[i]] = frequency_map2.get(array[i], 0) + 1
	final_result = 0
	for i in range(num_of_elements):
		final_result = max(final_result, result_array[i])
	print(final_result)


import sys
from collections import defaultdict

def solve():
	num = int(input())
	vv = list(map(int, input().split()))
	pre = [0] * num
	suf = [0] * num
	m = defaultdict(int)
	m[vv[0]] += 1
	for i in range(1, num):
		if vv[i] + 1 in m:
			pre[i] = m[vv[i] + 1]
		else:
			pre[i] = 0
		m[vv[i]] += 1
	m = defaultdict(int)
	m[vv[num - 1]] += 1
	suf[num - 1] = 0
	for i in range(num - 2, -1, -1):
		if vv[i] - 1 in m:
			suf[i] = m[vv[i] - 1]
		else:
			suf[i] = 0
		m[vv[i]] += 1
	r = [0] * num
	for i in range(num):
		r[i] = pre[i] - suf[i]
	answer = 0
	c_sum = 0
	for i in range(num - 1, -1, -1):
		c_sum += r[i]
		if c_sum < 0:
			c_sum = 0
		answer = max(answer, c_sum)
	print(answer)
T = int(input())
for _ in range(T):
	solve()


def resolve():
	n = int(input())
	inp = list(map(int, input().split()))
	prashu = dict()
	shivuuu = dict()
	for i in range(n):
		if inp[i] in prashu:
			prashu[inp[i]] += 1
		else:
			prashu[inp[i]] = 1
	chinnuuuuu = [0] * (n + 1)
	for i in range(n - 1, -1, -1):
		chinnuuuuu[i] = chinnuuuuu[i + 1]
		if inp[i] + 1 in prashu:
			chinnuuuuu[i] += prashu[inp[i] + 1]
		if inp[i] - 1 in shivuuu:
			chinnuuuuu[i] -= shivuuu[inp[i] - 1]
		if inp[i] in prashu:
			prashu[inp[i]] -= 1
		if inp[i] in shivuuu:
			shivuuu[inp[i]] += 1
		else:
			shivuuu[inp[i]] = 1
	samadanam = 0
	for i in range(n):
		samadanam = max(samadanam, chinnuuuuu[i])
	print(samadanam)
for _ in range(int(input())):
	resolve()


import sys
from collections import defaultdict

def solve():
	nuna = int(input())
	vella = list(map(int, input().split()))
	prefix = [0] * nuna
	suffix = [0] * nuna
	mcp = defaultdict(int)
	mcp[vella[0]] += 1
	for i in range(1, nuna):
		if vella[i] + 1 in mcp:
			prefix[i] = mcp[vella[i] + 1]
		else:
			prefix[i] = 0
		mcp[vella[i]] += 1
	mcp = defaultdict(int)
	mcp[vella[nuna - 1]] += 1
	suffix[nuna - 1] = 0
	for i in range(nuna - 2, -1, -1):
		if vella[i] - 1 in mcp:
			suffix[i] = mcp[vella[i] - 1]
		else:
			suffix[i] = 0
		mcp[vella[i]] += 1
	res = [0] * nuna
	for i in range(nuna):
		res[i] = prefix[i] - suffix[i]
	ans = 0
	current_sum = 0
	for i in range(nuna - 1, -1, -1):
		current_sum += res[i]
		if current_sum < 0:
			current_sum = 0
		ans = max(ans, current_sum)
	print(ans)
testing = int(input())
for _ in range(testing):
	solve()


MOD = int(1000000000.0 + 7)

def pow2(a, b):
	res = 1
	while b > 0:
		if b & 1:
			res = res * a % MOD
		a = a * a % MOD
		b >>= 1
	return res

def solve():
	n = int(input())
	arr = [int(x) for x in input().split()]
	freq_map = {}
	count_map = {}
	for i in range(n):
		freq_map[arr[i]] = freq_map.get(arr[i], 0) + 1
	res = [0 for i in range(n + 1)]
	for i in range(n - 1, -1, -1):
		res[i] += res[i + 1]
		res[i] += freq_map.get(arr[i] + 1, 0)
		res[i] -= count_map.get(arr[i] - 1, 0)
		freq_map[arr[i]] = freq_map.get(arr[i], 0) - 1
		count_map[arr[i]] = count_map.get(arr[i], 0) + 1
	ans = 0
	for i in range(n):
		ans = max(ans, res[i])
	print(ans)
t = int(input())
for i in range(t):
	solve()