Find the length of the longest contiguous segment in an array, in which if a given element $K$ is inserted, $K$ becomes the second largest element of that subarray.

-----Input:-----
- The first line will contain $T$, number of test cases. Then the test cases follow. 
- The first line of each test case contains two integers $N$ and $K$.
- The next line contains N space-separated integers Ai denoting the elements of the array.

-----Output:-----
Print a single line corresponding to each test case — the length of the largest segment.

-----Constraints-----
- $1 \leq T \leq 10$
- $1 \leq N \leq 10^6$
- $1 \leq Ai, K \leq 10^9$
- Sum of N across all test cases doesn't exceed $10^6$

-----Sample Input:-----
2
5 3
2 4 2 4 2
8 5
9 3 5 7 8 11 17 2

-----Sample Output:-----
5
3

-----EXPLANATION:-----
If 3 is inserted at anywhere in the array, it is the second largest element. Hence the maximum length is 5.
If 5 is inserted anywhere between 1st and 4th element, it is the second largest element. The length of such subarray is 3.

Source: codechef | Difficulty: HARD
Tags: Combinatorics

Amortized analysis

Mathematics


Solutions:
import sys
from sys import stdin, stdout
t = int(stdin.readline())
for _ in range(t):
	(n, k) = map(int, stdin.readline().strip().split(' '))
	arr = list(map(int, stdin.readline().strip().split(' ')))
	tarr = []
	p = -1
	for i in range(len(arr)):
		if arr[i] > k:
			if p == -1:
				p = arr[i]
				tarr.append(i)
			elif arr[i] != p:
				tarr.append(i)
				p = arr[i]
	if len(tarr) == 0:
		print(0)
	elif len(tarr) == 1:
		print(len(arr))
	else:
		mtn = max(tarr[1], +len(tarr) - tarr[-2] - 1)
		for i in range(1, len(tarr) - 1):
			mtn = max(mtn, tarr[i] - tarr[i - 1] + tarr[i + 1] - tarr[i] - 1)
		print(mtn)


a = int(input())
for i in range(a):
	cc = list(map(int, input().split()))
	dd = list(map(int, input().split()))
	for i in range(len(dd)):
		dd[i] -= cc[1]
	maxs = 0
	i = 0
	k = 0
	while i < len(dd):
		j = i + 1
		if dd[i] > 0:
			count = 1 + (i - k)
			k = i + 1
			while j < len(dd) and (dd[j] <= 0 or dd[j] == dd[i]):
				if dd[j] == dd[i]:
					k = j + 1
				count += 1
				j += 1
			if count > maxs:
				maxs = count
		i = j
	print(maxs)


for i in range(int(input())):
	(n, k) = input().split()
	n = int(n)
	k = int(k)
	arr = list(map(int, input().split()))
	a = 0
	b = 0
	count = 0
	ans = 0
	temp = -1
	w = 0
	index1 = index2 = None
	while b < n:
		if arr[b] > k:
			if count == 0:
				index1 = b
				count += 1
			elif arr[b] == arr[index1]:
				index1 = b
			else:
				index2 = b
				count += 1
		if count == 2:
			w = 1
			ans = max(ans, b - a)
			a = index1 + 1
			index1 = index2
			index2 = None
			count = 1
		b += 1
	if w == 0 and count == 1:
		print(n)
	else:
		print(ans)


t = int(input())
for i in range(t):
	(n, k) = map(int, input().strip().split())
	a = list(map(int, input().strip().split()))
	c = 0
	x = 0
	b = list()
	i1 = 0
	i2 = 0
	for j in range(n):
		c += 1
		if a[j] > k:
			x += 1
			if x == 1:
				i1 = j
			elif a[j] == a[i1]:
				x -= 1
			else:
				i2 = j
		if x == 2:
			x = 1
			b.append(c - 1)
			c = i2 - i1
			i1 = i2
			i2 = 0
		if j == n - 1 and b == []:
			b.append(n)
	print(max(b))


import sys

def _int():
	return int(sys.stdin.readline())

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

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

def _str():
	return sys.stdin.readline()

def _strarr():
	return sys.stdin.readline().split()
t = _int()
ans = []
for _ in range(t):
	(n, m) = _ints()
	arr = _intarr()
	start = -1
	end = -1
	index = -1
	ans = 0
	for i in range(n):
		if start == -1:
			start = i
			if arr[i] > m:
				index = i
		elif arr[i] > m:
			if index == -1:
				index = i
			elif arr[index] != arr[i]:
				end = i
				ans = max(ans, end - start)
				start = index + 1
			index = i
	if end != n - 1:
		end = n
		ans = max(ans, end - start)
	print(ans)


def solve(arr, n, k):
	if max(arr) <= k:
		return 0
	ans = 0
	m = -1
	f = 0
	i = 0
	j = -1
	while j < n - 1:
		if arr[j + 1] <= k:
			j += 1
		elif arr[j + 1] > k:
			if m == -1:
				m = arr[j + 1]
				f += 1
				j += 1
			elif arr[j + 1] == m:
				f += 1
				j += 1
			else:
				ans = max(ans, j - i + 1)
				while f:
					if arr[i] == m:
						f -= 1
					i += 1
				m = -1
				f = 0
	ans = max(ans, j - i + 1)
	return ans
for _ in range(int(input())):
	(n, k) = list(map(int, input().split()))
	arr = list(map(int, input().split()))
	print(solve(arr, n, k))


t = int(input())
while t:
	a = input().split()
	n = int(a[0])
	k = int(a[1])
	lst = input().split()
	for i in range(n):
		lst[i] = int(lst[i])
	greater = 0
	length = 0
	pos = -1
	allTimeLong = 0
	for i in range(n):
		if lst[i] > k and greater != 0 and (lst[i] != greater):
			greater = lst[i]
			if allTimeLong < length:
				allTimeLong = length
			length = i - pos
			pos = i
			continue
		elif lst[i] > k:
			greater = lst[i]
			pos = i
		length += 1
	if allTimeLong < length:
		allTimeLong = length
	t -= 1
	print(allTimeLong)


t = int(input())
for _ in range(t):
	(n, k) = list(map(int, input().strip().split()))
	a = list(map(int, input().strip().split()))
	c = 0
	f = 0
	b = []
	d = [0, 0]
	for i in range(n):
		if a[i] > k:
			f += 1
			if f == 1:
				d[0] = i
			elif a[i] == a[d[0]]:
				f -= 1
			else:
				d[1] = i
		c += 1
		if f == 2:
			f = 1
			b.append(c - 1)
			c = d[1] - d[0]
			d[0] = d[1]
			d[1] = 0
	if len(b) == 0:
		print(c)
	else:
		print(max(b))


for _ in range(int(input())):
	(n, k) = list(map(int, input().split()))
	a = list(map(int, input().split()))

	def check(mid):
		(d, left) = ({}, 0)
		for i in range(mid):
			if a[i] > k:
				if a[i] not in d:
					d[a[i]] = 1
				else:
					d[a[i]] += 1
		if len(d) == 1:
			return True
		for i in range(mid, n):
			if a[left] > k:
				d[a[left]] -= 1
				if d[a[left]] == 0:
					del d[a[left]]
			if a[i] > k:
				if a[i] not in d:
					d[a[i]] = 1
				else:
					d[a[i]] += 1
			if len(d) == 1:
				return True
			left += 1
		return False
	(lo, hi) = (0, n)
	while lo <= hi:
		mid = (lo + hi) // 2
		if check(mid):
			res = mid
			lo = mid + 1
		else:
			hi = mid - 1
	print(res)


T = int(input())
for q in range(T):
	(n, m) = map(int, input().strip().split())
	arr = list(map(int, input().strip().split()))
	c = 0
	ind = []
	mp = {}
	k = 0
	h = 0
	arr.append(max(arr) + 1)
	for i in range(n + 1):
		if arr[i] <= m:
			c += 1
		elif h == 0:
			h = 1
			k = i
			c += 1
		elif arr[k] == arr[i]:
			c += 1
			k = i
		else:
			ind.append(c)
			c = max(1, i - k)
			k = i
	if len(ind) == 0:
		print(0)
	else:
		print(max(ind))


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	lt = list()
	nos = list()
	p = -1
	for j in range(n):
		if a[j] > k:
			nos.append(a[j])
			lt.append(j + 1)
	lt = [0] + lt + [n + 1]
	(l, j) = (0, 0)
	tm = len(lt)
	nos = [0] + nos + [nos[tm - 3]]
	while j < tm - 2:
		xt = j + 2
		while xt + 1 < tm and nos[xt] == nos[j + 1]:
			xt += 1
		ct = lt[xt] - lt[j] - 1
		if ct > l:
			l = ct
		j = xt - 1
	print(l)


for _ in range(int(input())):
	(n, k) = list(map(int, input().split()))
	a = list(map(int, input().split()))
	c = 0
	d = {}
	l = 0
	r = 0
	sm = 0
	m = 1
	i = 0
	while i < n:
		if a[i] > k:
			if a[i] not in d or d[a[i]] == -1:
				c += 1
			d[a[i]] = i
			if c > 1:
				l = d[sm] + 1
				d[sm] = -1
				c -= 1
			sm = a[i]
		r += 1
		i += 1
		if r - l > m:
			m = r - l
	print(m)


t = int(input())
while t > 0:
	(n, k) = [int(x) for x in input().split()]
	a = [int(x) for x in input().split()]
	first = 0
	prev = 0
	i = 0
	len = 0
	maxlen = 0
	while i < n:
		if a[i] > k:
			if first == 0:
				first = a[i]
				prev = i
				len += 1
			elif first == a[i]:
				len += 1
				prev = i
			else:
				first = 0
				i = prev
				if maxlen < len:
					maxlen = len
				len = 0
		else:
			len += 1
		i += 1
	else:
		if maxlen < len:
			maxlen = len
	print(maxlen)
	t -= 1


for _ in range(int(input())):
	(n, k) = list(map(int, input().split()))
	l = [int(i) for i in input().split()]
	maxi = 0
	grtr = 0
	st = 0
	from collections import defaultdict
	big = defaultdict(int)
	for end in range(n):
		if l[end] > k:
			big[l[end]] += 1
			if big[l[end]] == 1:
				grtr += 1
		while grtr > 1:
			if l[st] > k:
				big[l[st]] -= 1
				if big[l[st]] <= 0:
					grtr -= 1
			st += 1
		maxi = max(maxi, end - st + 1)
	print(maxi)


t = int(input())
for j in range(t):
	(n, k) = list(map(int, input().split()))
	a = list(map(int, input().split()))
	mm = 0
	x = 1
	l = 0
	m = -1
	for i in range(n):
		if x == 1:
			if a[i] > k:
				c = i
				l = l + 1
				m = a[i]
				x = 0
				continue
		if a[i] <= k or a[i] == m:
			if a[i] == m:
				c = i
			l = l + 1
			if l > mm:
				mm = l
		else:
			if l > mm:
				mm = l
			l = i - c
			c = i
			if l > mm:
				mm = l
			m = a[i]
	print(mm)


def answer():
	for t in range(int(input())):
		(N, K) = [int(x) for x in input().split()]
		l = [-1]
		l += [int(x) for x in input().split()]
		green = 0
		orange = 0
		red = 0
		ans = 0
		while True:
			orange += 1
			if orange == N + 1:
				ans = max(ans, N - green)
				break
			elif l[orange] > K:
				red = orange
				while True:
					red += 1
					if red == N + 1:
						ans = max(ans, N - green)
						break
					elif l[red] > K:
						if l[red] != l[orange]:
							ans = max(ans, red - green - 1)
							green = orange
							orange = red - 1
							break
						else:
							orange = red
		print(ans)
	return
answer()


for i in range(int(input())):
	(n, k) = map(int, input().split())
	(flag, prevhidx, prevh) = (0, 0, 0)
	(urr, mx) = (0, 0)
	idx = []
	a = list(map(int, input().split()))
	for i in range(n):
		if a[i] > k:
			if flag == 0:
				flag = 1
				prevhidx = i
				prevh = a[i]
				urr += 1
			elif a[i] == prevh:
				prevhidx = i
				urr += 1
			else:
				if urr > mx:
					mx = urr
				urr = i - prevhidx
				prevh = a[i]
				prevhidx = i
		else:
			urr += 1
	if urr > mx:
		mx = urr
	if flag == 1:
		print(mx)
	else:
		print(flag)


for _ in range(int(input())):
	(n, k) = list(map(int, input().split()))
	ays = list(map(int, input().split()))
	gt = k
	gtp = -1
	mseg = 0
	seg = 0
	for (ax, a) in enumerate(ays):
		if a <= k:
			seg += 1
		elif a == gt:
			seg += 1
			gtp = ax
		else:
			if seg > mseg:
				mseg = seg
			gt = a
			seg = ax - gtp
			gtp = ax
	if gt == k:
		mseg = 0
	elif seg > mseg:
		mseg = seg
	print(mseg)


for _ in range(int(input())):
	(n, k) = list(map(int, input().split()))
	arr = list(map(int, input().split()))
	if n == 1:
		if arr[0] >= k:
			print(2)
		else:
			print(1)
	elif n == 2:
		(mx, mn) = (max(arr[0], arr[1]), min(arr[0], arr[1]))
		if mn >= k:
			if mx == mn:
				print(2)
			else:
				print(1)
		elif mx >= k > mn:
			print(1)
		else:
			print(0)
	else:
		mx = 0
		count = 0
		f = 0
		f_pos = -1
		for (pos, num) in enumerate(arr):
			if f == 0:
				if num >= k:
					f = num
					f_pos = pos
				count += 1
			elif num <= k:
				count += 1
			elif num == f:
				count += 1
			else:
				count = pos - f_pos
				f_pos = pos
			if count > mx:
				mx = count
		print(mx)


T = int(input())
for _ in range(T):
	(N, K) = map(int, input().split())
	A = list(map(int, input().split()))
	lower = []
	ans = []
	if A[0] > K:
		ans.append(1)
		lower.append(0)
		M = A[0]
	else:
		ans.append(0)
		lower.append(1)
	for i in range(1, N):
		if A[i] > K:
			if ans[-1] != 0:
				if M == A[i]:
					ans.append(ans[-1] + 1)
				else:
					ans.append(lower[-1] + 1)
					M = A[i]
			else:
				ans.append(lower[-1] + 1)
				M = A[i]
			lower.append(0)
		else:
			if ans[-1] != 0:
				ans.append(ans[-1] + 1)
			else:
				ans.append(0)
			lower.append(lower[-1] + 1)
	print(max(ans))


t = int(input())
for it in range(t):
	(n, k) = input().split(' ')
	n = int(n)
	k = int(k)
	stdin = input().split(' ')
	a = [int(stdin[i]) for i in range(n)]
	state = 0
	mx = 0
	count = 0
	maxe = -1
	pos = -1
	i = 0
	while i < n:
		if state == 0:
			count += 1
			if a[i] > k:
				state = 1
				pos = i
				maxe = a[i]
		elif a[i] <= k or a[i] == maxe:
			count += 1
			if a[i] == maxe:
				pos = i
		else:
			mx = max(mx, count)
			count = i - pos
			pos = i
			maxe = a[i]
		i += 1
	if state != 0:
		mx = max(mx, count)
	print(mx)


for _ in range(int(input())):
	input_list = input().split()
	(N, K) = (int(input_list[0]), int(input_list[1]))
	A = list(map(int, input().split()))
	index = []
	greater_elem = -1
	for i in range(0, N):
		if A[i] > K and A[i] != greater_elem:
			index.append(i)
			greater_elem = A[i]
	if len(index) == 0:
		print(0)
	elif len(index) == 1:
		print(N)
	elif len(index) == 2:
		print(index[1] - index[0])
	else:
		max_sublen = 0
		for i in range(len(index) - 2):
			max_sublen = max(max_sublen, index[i + 2] - index[i] - 1)
		print(max_sublen)