Read problem statements in [Bengali], [Mandarin Chinese], [Russian], and [Vietnamese] as well.

The young but promising paparazzi Gennady wants to finally become famous. To do this, he wants to take a picture of a new super star during her walk in the mountains.

It is known that the star's path in the mountains consists of $N$ sections. For each valid $i$, the $i$-th section is a vertical half-open interval with coordinates $x = i$ and $y \in [0, h_{i})$.

For each valid $i$ and $j$, our hero can take a picture of the star located in the $i$-th section of the walk when he is in the $j$-th section only if he can see the star ― that is, $i < j$ and for each $k$ ($i < k < j$), the half-open interval that makes up the $k$-th section must not intersect the line segment $[(i, h_{i}), (j, h_{j})]$.

Gennady is a paparazzi, not a programmer, so he asks you to determine the maximum distance from which he can take a picture of the star, which is the maximum value of $j-i$ over all pairs $(i, j)$. Help him become famous!

------  Input ------
The first line of the input contains a single 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$.
The second line contains $N$ space-separated integers $h_{1}, h_{2}, \ldots, h_{N}$.

------  Output ------
For each test case, print a single line containing one integer ― the maximum distance.

------  Constraints ------
$1 ≤ T ≤ 10^{4}$
$2 ≤ N ≤ 5 \cdot 10^{5}$
$1 ≤ h_{i} ≤ 10^{9}$ for each valid $i$
the sum of $N$ over all test cases does not exceed $5 \cdot 10^{5}$

------  Subtasks ------
Subtask #1 (10 points): the sum of $N$ over all test cases does not exceed $500$

Subtask #2 (10 points): the sum of $N$ over all test cases does not exceed $8,000$

Subtask #3 (80 points): original constraints

----- Sample Input 1 ------ 
4

2

1 2

3

1 2 3

7

3 2 5 3 2 4 3

8

1 2 4 3 5 4 2 1
----- Sample Output 1 ------ 
1

2

3

2
----- explanation 1 ------ 
Example case 3:

Difficulty: MEDIUM_HARD
Tags: Sweep line algorithms

Starter code:

Solutions:
t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	ans = 1
	s = []
	p = []
	for j in range(n):
		p.append([j + 1, a[j]])
	if n == 2:
		print(1)
	else:
		s.append(p[0])
		s.append(p[1])
		x = len(s)
		for z in range(2, n):
			while x > 1:
				s1 = (s[x - 1][1] - s[x - 2][1]) / (s[x - 1][0] - s[x - 2][0])
				s2 = (p[z][1] - s[x - 1][1]) / (p[z][0] - s[x - 1][0])
				if s1 <= s2:
					s.pop()
					x -= 1
				else:
					break
			s.append(p[z])
			x += 1
			ans = max(ans, s[x - 1][0] - s[x - 2][0])
		print(ans)


for _ in range(int(input())):
	N = int(input())
	A = list(map(int, input().split()))
	ans = 1
	s = []
	p = []
	for i in range(N):
		p.append([i + 1, A[i]])
	if N == 2:
		print(1)
	else:
		s.append(p[0])
		s.append(p[1])
		size = len(s)
		for i in range(2, N):
			while size > 1:
				s1 = (s[size - 1][1] - s[size - 2][1]) / (s[size - 1][0] - s[size - 2][0])
				s2 = (p[i][1] - s[size - 1][1]) / (p[i][0] - s[size - 1][0])
				if s1 <= s2:
					s.pop()
					size -= 1
				else:
					break
			s.append(p[i])
			size += 1
			ans = max(ans, s[size - 1][0] - s[size - 2][0])
		print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	p = []
	st = []
	ar = list(map(int, input().split()))
	for i in range(n):
		p.append([i + 1, ar[i]])
	if n == 2:
		print(1)
	else:
		st.append(p[0])
		st.append(p[1])
		ans = 1
		sz = len(st)
		for i in range(2, n):
			while len(st) >= 2:
				s1 = (st[sz - 1][1] - st[sz - 2][1]) / (st[sz - 1][0] - st[sz - 2][0])
				s2 = (p[i][1] - st[sz - 1][1]) / (p[i][0] - st[sz - 1][0])
				if s1 <= s2:
					st.pop()
					sz -= 1
				else:
					break
			st.append(p[i])
			sz += 1
			ans = max(ans, st[sz - 1][0] - st[sz - 2][0])
		print(ans)


import math

def func(n, a):
	store = []
	s = 0
	store.append((1, a[0]))
	store.append((2, a[1]))
	s = 2
	ans = store[1][0] - store[0][0]
	for i in range(2, n):
		while s >= 2 and (a[i] - store[s - 1][1]) / (i + 1 - store[s - 1][0]) >= (store[s - 1][1] - store[s - 2][1]) / (store[s - 1][0] - store[s - 2][0]):
			store.pop(s - 1)
			s -= 1
		ans = max(ans, i + 1 - store[s - 1][0])
		store.append((i + 1, a[i]))
		s += 1
	return ans
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	print(func(n, a))


def canSee(a, b, c, array):
	return (array[c] - array[b]) * (b - a) >= (array[b] - array[a]) * (c - b)
for _ in range(int(input())):
	n = int(input())
	array = list(map(int, input().split()))
	(stack, answer) = ([0, 1], 0)
	for i in range(2, n):
		while len(stack) > 1 and canSee(stack[-2], stack[-1], i, array):
			stack.pop()
		stack.append(i)
	while len(stack) > 1:
		top = stack.pop()
		answer = max(answer, top - stack[-1])
	print(answer)


import math

def direction(a, b, c):
	return (b.x - a.x) * (c.y - b.y) - (b.y - a.y) * (c.x - b.x)

def posDeg(x):
	if x < 0:
		return 180 - abs(x)
	return x

def inDeg(pt1, pt2):
	if pt1.x == pt2.x and pt1.y == pt2.y:
		return 0
	num = pt2.y - pt1.y
	den = pt2.x - pt1.x
	if den != 0:
		return posDeg(math.degrees(math.atan(num / den)))
	else:
		return 90

class Point:

	def __init__(self, x, y, deg=0):
		self.x = x
		self.y = y
		self.deg = deg

def convex_hull(pts):
	btm = 0
	for i in range(1, n):
		if pts[i].y < pts[btm].y:
			btm = i
	for i in range(n):
		pts[i].deg = inDeg(pts[btm], pts[i])
	pts.sort(key=lambda x: x.deg)
	s = []
	s.append(pts[0])
	s.append(pts[1])
	direc = 0
	k = 2
	while k < n:
		direc = direction(s[-2], s[-1], pts[k])
		if direc > 0:
			s.append(pts[k])
			k += 1
		elif direc == 0:
			s.pop()
			s.append(pts[k])
			k += 1
		else:
			s.pop()
	return s
for _ in range(int(input())):
	n = int(input())
	y = list(map(int, input().split()))
	x = range(1, n + 1)
	pts = []
	for i in range(n):
		pts.append(Point(x[i], y[i]))
	ans = convex_hull(pts)
	ans.sort(key=lambda z: z.x)
	upper = []
	for p in reversed(ans):
		while len(upper) >= 2 and direction(upper[-2], upper[-1], p) <= 0:
			upper.pop()
		upper.append(p)
	upper.sort(key=lambda z: z.x)
	mxdist = 0
	for i in range(len(upper) - 1):
		mxdist = max(mxdist, abs(upper[i + 1].x - upper[i].x))
	print(mxdist)


def getMaxSlope(i, j, N, H):
	s = -float('inf')
	si = j
	for x in range(j, N):
		slope = (H[x] - H[i]) / (x - i)
		if slope >= s:
			s = slope
			si = x
	return si
T = int(input())
ans = []
for _ in range(T):
	N = int(input())
	H = [int(i) for i in input().split()]
	i = 0
	j = 1
	maxdist = 1
	while i < N:
		j = getMaxSlope(i, j, N, H)
		if j - i > maxdist:
			maxdist = j - i
		i = j
		j += 1
	ans.append(maxdist)
for i in ans:
	print(i)


t = int(input())
for i in range(t):
	n = int(input())
	arr = [int(x) for x in input().split()]
	p = []
	stk = []
	for i in range(len(arr)):
		p.append([i + 1, arr[i]])
	if n <= 2:
		print(1)
	else:
		stk.append(p[0])
		stk.append(p[1])
		length = len(stk)
		ans = 1
		for i in range(2, n):
			while length >= 2:
				slope1 = (stk[length - 1][1] - stk[length - 2][1]) / (stk[length - 1][0] - stk[length - 2][0])
				slope2 = (p[i][1] - stk[length - 1][1]) / (p[i][0] - stk[length - 1][0])
				if slope2 < slope1:
					break
				else:
					stk.pop()
					length -= 1
			stk.append(p[i])
			length += 1
			ans = max(ans, stk[length - 1][0] - stk[length - 2][0])
		print(ans)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = []
	for i in range(n):
		t = [i, a[i]]
		b.append(t)
	c = []
	c.append(b[0])
	c.append(b[1])
	l = 2
	p = 1
	for i in range(2, n):
		while len(c) >= 2:
			slope1 = (c[l - 1][1] - c[l - 2][1]) / (c[l - 1][0] - c[l - 2][0])
			slope2 = (b[i][1] - c[l - 1][1]) / (b[i][0] - c[l - 1][0])
			if slope1 <= slope2:
				c.pop()
				l = l - 1
			else:
				break
		c.append(b[i])
		l = l + 1
		p = max(p, c[l - 1][0] - c[l - 2][0])
	print(p)


test = int(input())
for e in range(test):
	n = int(input())
	l = list(map(int, input().split()))
	p = []
	stk = []
	for i in range(n):
		p.append([i + 1, l[i]])
	if n != 2:
		stk.append(p[0])
		stk.append(p[1])
		ans = 1
		ln = len(stk)
		for i in range(2, n):
			while len(stk) >= 2:
				s1 = (stk[ln - 1][1] - stk[ln - 2][1]) / (stk[ln - 1][0] - stk[ln - 2][0])
				s2 = (p[i][1] - stk[ln - 1][1]) / (p[i][0] - stk[ln - 1][0])
				if s1 > s2:
					break
				else:
					stk.pop()
					ln -= 1
			stk.append(p[i])
			ln += 1
			ans = max(ans, stk[ln - 1][0] - stk[ln - 2][0])
		print(ans)
	else:
		print(1)


for _ in range(int(input())):
	n = int(input())
	array = list(map(int, input().split()))
	if n <= 2:
		print(1)
	else:
		answere = 1
		a = []
		for i in range(n):
			a.append([i + 1, array[i]])
		b = []
		b.append(a[0])
		b.append(a[1])
		l = len(b)
		for i in range(2, n):
			while l >= 2:
				s1 = (b[l - 1][1] - b[l - 2][1]) / (b[l - 1][0] - b[l - 2][0])
				s2 = (b[l - 1][1] - a[i][1]) / (b[l - 1][0] - a[i][0])
				if s2 >= s1:
					b.pop()
					l -= 1
				else:
					break
			b.append(a[i])
			l += 1
			answere = max(answere, b[l - 1][0] - b[l - 2][0])
		print(answere)


import math

def left_right(pa, pb, pc):
	xa = pa[0]
	ya = pa[1]
	xb = pb[0]
	yb = pb[1]
	xc = pc[0]
	yc = pc[1]
	return (xb - xa) * (yc - ya) - (xc - xa) * (yb - ya)

def graham_hull(h_vec):
	points = [[i, h_vec[i]] for i in range(len(h_vec))]
	stack = [points[0], points[-1]]
	for i in range(len(points) - 2, -1, -1):
		while len(stack) > 2 and left_right(stack[-2], stack[-1], points[i]) <= 0:
			stack.pop()
		stack.append(points[i])
	if stack[-1] == stack[0]:
		stack = stack[0:-1]
	stack.sort(key=lambda x: x[0])
	stack = [s[0] for s in stack]
	return stack

def jarvis_march(h_vec):
	n = len(h_vec)
	hull = [0]
	index = 0
	while index < n - 1:
		x1 = index
		y1 = h_vec[index]
		max_alpha = -math.inf
		max_index = None
		for j in range(index + 1, n):
			x2 = j
			y2 = h_vec[j]
			alpha = None
			if y1 == y2:
				alpha = 90
			elif y1 > y2:
				alpha = 90 - 180 * math.atan((y1 - y2) / (x2 - x1)) / math.pi
			elif y1 < y2:
				alpha = 90 + 180 * math.atan((y2 - y1) / (x2 - x1)) / math.pi
			if max_alpha <= alpha:
				max_alpha = alpha
				max_index = j
		index = max_index
		hull.append(max_index)
	return hull
t = int(input())
for _ in range(t):
	n = int(input())
	h_vec = input().split(' ')
	h_vec = [int(h) for h in h_vec]
	hull = graham_hull(h_vec)
	diff = 0
	for i in range(1, len(hull)):
		delta = hull[i] - hull[i - 1]
		if diff < delta:
			diff = delta
	print(diff)


import math

def left_right(pa, pb, pc):
	xa = pa[0]
	ya = pa[1]
	xb = pb[0]
	yb = pb[1]
	xc = pc[0]
	yc = pc[1]
	return (xb - xa) * (yc - ya) - (xc - xa) * (yb - ya)

def graham_hull(h_vec):
	points = [[i, h_vec[i]] for i in range(len(h_vec))]
	stack = [points[0], points[-1]]
	for i in range(len(points) - 2, -1, -1):
		while len(stack) > 2 and left_right(stack[-2], stack[-1], points[i]) <= 0:
			stack.pop()
		stack.append(points[i])
	if stack[-1] == stack[0]:
		stack = stack[0:-1]
	stack.sort(key=lambda x: x[0])
	stack = [s[0] for s in stack]
	return stack
t = int(input())
for _ in range(t):
	n = int(input())
	h_vec = input().split(' ')
	h_vec = [int(h) for h in h_vec]
	hull = graham_hull(h_vec)
	diff = 0
	for i in range(1, len(hull)):
		delta = hull[i] - hull[i - 1]
		if diff < delta:
			diff = delta
	print(diff)


def getOrientation(p0, p1, p2):
	val = float((p1[0] - p0[0]) * (p2[1] - p0[1])) - float((p1[1] - p0[1]) * (p2[0] - p0[0]))
	return val
for _ in range(int(input())):
	n = int(input())
	h = list(map(int, input().split()))
	points = []
	for i in range(n):
		points.append([i, h[i]])
	ans = 1
	stack = [points[0], points[1]]
	stack_size = 2
	for i in range(2, n):
		while stack_size > 1:
			d = getOrientation(stack[-2], stack[-1], points[i])
			if d >= 0:
				stack.pop()
				stack_size -= 1
			else:
				break
		stack_size += 1
		ans = max(ans, points[i][0] - stack[-1][0])
		stack.append(points[i])
	print(ans)


def slope(point1, point2):
	return (point2[1] - point1[1]) / (point2[0] - point1[0])
	pass
for _ in range(int(input())):
	N = int(input())
	p = list(map(int, input().split()))
	points = [(i + 1, p[i]) for i in range(N)]
	reach = [points[0], points[1]]
	ans = 1
	for i in range(2, N):
		while len(reach) >= 2:
			if slope(reach[-1], points[i]) >= slope(reach[len(reach) - 2], reach[-1]):
				reach.pop()
			else:
				break
		ans = max(ans, points[i][0] - reach[-1][0])
		reach.append(points[i])
	print(ans)


from collections import deque

def orientation(p1, p2, p3):
	v = (p2[1] - p1[1]) * (p3[0] - p2[0]) - (p3[1] - p2[1]) * (p2[0] - p1[0])
	if v == 0:
		return 0
	if v > 0:
		return 1
	else:
		return 2
t = int(input())
for _ in range(t):
	n = int(input())
	h = [int(i) for i in input().split()]
	s = deque()
	s.append((1, h[0]))
	s.append((2, h[1]))
	for i in range(2, n):
		while len(s) != 1:
			p2 = s.pop()
			p1 = s[-1]
			if orientation(p1, p2, (i + 1, h[i])) == 1:
				s.append(p2)
				break
		s.append((i + 1, h[i]))
	ans = 0
	i = 1
	while i < len(s):
		ans = max(ans, s[i][0] - s[i - 1][0])
		i += 1
	print(ans)


from typing import List

def solve(N: int, sections: List[int]) -> int:
	max_dist = 0
	i = 0
	while i < N:
		slope = -float('inf')
		k = i + 1
		for j in range(k, N):
			new_slope = (sections[j] - sections[i]) / (j - i)
			if new_slope >= slope:
				max_dist = max(max_dist, j - i)
				k = j
				slope = new_slope
		i = k
	return max_dist
t = int(input())
for _ in range(t):
	n = int(input())
	sections = list(map(int, input().split()))
	print(solve(n, sections))


def crossproduct(l, c):
	a = l[-2]
	b = l[-1]
	return (b[0] - a[0]) * (c[1] - a[1]) - (b[1] - a[1]) * (c[0] - a[0])
t = int(input())
for case in range(t):
	n = int(input())
	a = [int(i) for i in input().split()]
	l = [(i, a[i]) for i in range(n)]
	p = [l[0], l[1]]
	m = 1
	for i in range(2, n):
		while len(p) > 1 and crossproduct(p, l[i]) >= 0:
			p = p[:-1]
		m = max(m, l[i][0] - p[-1][0])
		p.append(l[i])
	print(m)


import sys
input = lambda : sys.stdin.readline().rstrip('\r\n')
inp = lambda : list(map(int, sys.stdin.readline().rstrip('\r\n').split()))
mod = 10 ** 9 + 7
Mod = 998244353
INF = float('inf')
tc = 1
tc = int(input())
for _ in range(tc):
	n = int(input())
	a = inp()

	def solve(a, n):
		stack = [[0, a[0]]]
		ans = 0

		def slope(b, c, d):
			slope1 = (d[1] - c[1]) / (d[0] - c[0])
			slope2 = (d[1] - b[1]) / (d[0] - b[0])
			return slope2 >= slope1
		for i in range(n):
			while len(stack) > 1 and slope(stack[-1], stack[-2], [i, a[i]]):
				stack.pop()
			res = i - stack[-1][0]
			ans = max(ans, res)
			stack.append([i, a[i]])
		return ans
	ans1 = solve(a, n)
	ans2 = solve(a[::-1], n)
	print(max(ans1, -1))


t = int(input())
for _ in range(t):
	n = int(input())
	ls = list(map(int, input().split()))
	convex_hull = [0]
	for i in range(1, len(ls)):
		if convex_hull[-1] == 0:
			convex_hull.append(i)
		else:
			m_prev = (ls[convex_hull[-2]] - ls[convex_hull[-1]]) / (convex_hull[-2] - convex_hull[-1])
			m_new = (ls[convex_hull[-1]] - ls[i]) / (convex_hull[-1] - i)
			while m_new >= m_prev:
				convex_hull.pop()
				if convex_hull[-1] == 0:
					break
				m_prev = (ls[convex_hull[-2]] - ls[convex_hull[-1]]) / (convex_hull[-2] - convex_hull[-1])
				m_new = (ls[convex_hull[-1]] - ls[i]) / (convex_hull[-1] - i)
			convex_hull.append(i)
	Max = 0
	for i in range(1, len(convex_hull)):
		Max = max(Max, convex_hull[i] - convex_hull[i - 1])
	print(Max)


def fun(arr, n):
	s = []
	s.append((0, arr[0]))
	s.append((1, arr[1]))

	def cross_product(i):
		(x, y) = s[-2]
		(x1, y1) = s[-1]
		(x2, y2) = (i, arr[i])
		return (x1 - x) * (y2 - y) - (x2 - x) * (y1 - y)
	ans = 1
	for i in range(2, n):
		while len(s) > 1 and cross_product(i) >= 0:
			s.pop()
		ans = max(ans, i - s[-1][0])
		s.append((i, arr[i]))
	print(ans)
t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	fun(arr, n)


import sys
import math
import bisect
import collections
input = sys.stdin.readline

def inp():
	return int(input())

def inplist():
	return list(map(int, input().split()))

def inpstrlist():
	s = input()
	return list(s[:len(s)])

def invr():
	return map(int, input().split())

def printlist(var):
	sys.stdout.write(' '.join(map(str, var)) + '\n')

class Point:

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

def orientation(p, q, r):
	val = (q.y - p.y) * (r.x - q.x) - (q.x - p.x) * (r.y - q.y)
	if val == 0:
		return 0
	elif val > 0:
		return 1
	else:
		return 2
for _ in range(int(input())):
	n = inp()
	arr = inplist()
	convexHull = [Point(0, arr[0]), Point(1, arr[1])]
	ans = 1
	for i in range(2, n):
		temp = Point(i, arr[i])
		while len(convexHull) > 1 and orientation(convexHull[-2], convexHull[-1], temp) != 1:
			convexHull.pop()
		ans = max(ans, i - convexHull[-1].x)
		convexHull.append(temp)
	print(ans)


slope = lambda t1, t2: (t2[1] - t1[1]) / (t2[0] - t1[0])
check = lambda t1, t2, t3: slope(t2, t3) < slope(t1, t2)

def grahamScan(arr, n):
	tarr = list(zip(range(n), arr))
	hull = tarr[:2]
	l = 2
	tarr = tarr[2:]
	for i in tarr:
		while not check(hull[-2], hull[-1], i):
			hull.pop()
			l -= 1
			if l == 1:
				break
		hull.append(i)
		l += 1
	(hull, _) = zip(*hull)
	dists = [hull[i] - hull[i - 1] for i in range(1, len(hull))]
	return max(dists)
t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	print(grahamScan(arr, n))


for _ in range(int(input())):
	N = int(input())
	arr = list(map(int, input().split()))
	stack1 = []
	stack2 = []
	if N == 2:
		print(1)
		continue
	for i in range(N):
		stack1.append([i + 1, arr[i]])
	stack2.extend([stack1[0], stack1[1]])
	ans = 1
	for i in range(2, N, 1):
		while len(stack2) >= 2:
			try:
				m1 = (stack2[-1][1] - stack2[-2][1]) / (stack2[-1][0] - stack2[-2][0])
			except ZeroDivisionError:
				m1 = 0
			try:
				m2 = (stack1[i][1] - stack2[-1][1]) / (stack1[i][0] - stack2[-1][0])
			except:
				m2 = 0
			if m1 <= m2:
				stack2.pop()
			else:
				break
		stack2.append(stack1[i])
		ans = max(ans, stack2[-1][0] - stack2[-2][0])
	print(ans)


for _ in range(int(input())):
	n = int(input())
	n_s = list(map(int, input().split()[:n]))
	n1 = []
	if n <= 2:
		print('1')
	else:
		for (i, c) in enumerate(n_s):
			n1.append([i, c])
		a = [n1[0], n1[1]]
		ans = 1
		for i in range(2, n, 1):
			while len(a) >= 2:
				slope1 = (a[-1][1] - a[-2][1]) / (a[-1][0] - a[-2][0])
				slope2 = (n1[i][1] - a[-1][1]) / (n1[i][0] - a[-1][0])
				if slope2 >= slope1:
					a = a[:-1]
				else:
					break
			a.append(n1[i])
			ans = max(ans, a[-1][0] - a[-2][0])
		print(ans)


for t in range(int(input())):
	n = int(input())
	h = list(map(int, input().split()))
	if n <= 2:
		print(1)
	else:
		ans = 1
		a = []
		for i in range(n):
			k = [i, h[i]]
			a.append(k)
		b = []
		b.append(a[0])
		b.append(a[1])
		l = len(b)
		for i in range(2, n, 1):
			while len(b) >= 2:
				s1 = (b[l - 1][1] - b[l - 2][1]) / (b[l - 1][0] - b[l - 2][0])
				s2 = (a[i][1] - b[l - 1][1]) / (a[i][0] - b[l - 1][0])
				if s1 <= s2:
					b.pop()
					l = l - 1
				else:
					break
			b.append(a[i])
			l = l + 1
			ans = max(ans, b[l - 1][0] - b[l - 2][0])
		print(ans)


t = int(input())
for e in range(t):
	n = int(input())
	l = input().split()
	p = []
	stk = []
	for i in range(n):
		l[i] = int(l[i])
		p.append([i + 1, l[i]])
	if n == 2:
		print('1')
		continue
	stk.append(p[0])
	stk.append(p[1])
	res = 1
	ln = len(stk)
	for i in range(2, n):
		while len(stk) >= 2:
			s1 = (stk[ln - 1][1] - stk[ln - 2][1]) / (stk[ln - 1][0] - stk[ln - 2][0])
			s2 = (p[i][1] - stk[ln - 1][1]) / (p[i][0] - stk[ln - 1][0])
			if s1 <= s2:
				stk.pop()
				ln -= 1
			else:
				break
		stk.append(p[i])
		ln += 1
		res = max(res, stk[ln - 1][0] - stk[ln - 2][0])
	print(res)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	ind = [i for i in range(n)]
	if n >= 4:
		(max1, max2) = (1, n - 2)
		for i in range(1, n - 2):
			if a[i] > a[max1]:
				max1 = i
		for i in range(n - 2, max1, -1):
			if a[i] > a[max2]:
				max2 = i
		a = a[:max1 + 1] + a[max2:]
		ind = ind[:max1 + 1] + ind[max2:]
		n = len(a)
	i = 1
	(a_t, ind_t) = ([a[0]], [ind[0]])
	while i < len(a) - 1:
		(x, y, x1, y1, x2, y2) = (ind[i], a[i], ind_t[-1], a_t[-1], ind[i + 1], a[i + 1])
		if not (y <= y1 and y <= y2 or y <= (y2 - y1) * (x - x1) / (x2 - x1) + y1):
			if len(a_t) >= 2:
				(x, y, x1, y1, x2, y2) = (ind_t[-1], a_t[-1], ind_t[-2], a_t[-2], ind[i], a[i])
			if len(a_t) >= 2 and (y <= y1 and y <= y2 or y <= (y2 - y1) * (x - x1) / (x2 - x1) + y1):
				a_t.pop()
				ind_t.pop()
			else:
				a_t.append(a[i])
				ind_t.append(ind[i])
				i += 1
		else:
			i += 1
	while True:
		if len(a_t) >= 2:
			(x, y, x1, y1, x2, y2) = (ind_t[-1], a_t[-1], ind_t[-2], a_t[-2], ind[-1], a[-1])
			if y <= y1 and y <= y2 or y <= (y2 - y1) * (x - x1) / (x2 - x1) + y1:
				a_t.pop()
				ind_t.pop()
			else:
				break
		else:
			break
	ind_t.append(ind[-1])
	m = ind_t[1] - ind_t[0]
	for i in range(1, len(ind_t)):
		x = ind_t[i] - ind_t[i - 1]
		if x > m:
			m = x
	print(m)


for _ in range(int(input())):
	n = int(input())
	h = list(map(int, input().split()))
	hlists = []
	slopelist = []
	ans = 1
	for i in range(n):
		hi = [i + 1, h[i]]
		hlists.append(hi)
	if n == 2:
		print('1')
		continue
	slopelist.append(hlists[0])
	slopelist.append(hlists[1])
	lens = len(slopelist)
	for i in range(2, n):
		while lens >= 2:
			s1 = (slopelist[lens - 1][1] - slopelist[lens - 2][1]) / (slopelist[lens - 1][0] - slopelist[lens - 2][0])
			s2 = (hlists[i][1] - slopelist[lens - 1][1]) / (hlists[i][0] - slopelist[lens - 1][0])
			if s1 <= s2:
				slopelist.pop()
				lens = lens - 1
			else:
				break
		slopelist.append(hlists[i])
		lens = lens + 1
		ans = max(ans, slopelist[lens - 1][0] - slopelist[lens - 2][0])
	print(ans)


t = int(input())
for i in range(t):
	n = int(input())
	p = []
	ST = []
	q = []
	q = list(map(int, input().split()))
	for j in range(n):
		temp = (j + 1, q[j])
		p.append(temp)
	if n == 2:
		print('1')
		continue
	ST.append(p[0])
	ST.append(p[1])
	ans = 1
	sl = len(ST)
	for j in range(2, n):
		while len(ST) >= 2:
			s1 = (ST[sl - 1][1] - ST[sl - 2][1]) / (ST[sl - 1][0] - ST[sl - 2][0])
			s2 = (p[j][1] - ST[sl - 1][1]) / (p[j][0] - ST[sl - 1][0])
			if s1 <= s2:
				ST.pop()
				sl -= 1
			else:
				break
		ST.append(p[j])
		sl += 1
		ans = max(ans, ST[sl - 1][0] - ST[sl - 2][0])
	print(ans)
	q.clear()


var1 = int(input())
for k in range(var1):
	var2 = int(input())
	l1 = list(map(int, input().split()))
	if var2 <= 2:
		print(1)
		continue
	out = 1
	l2 = []
	for j in range(var2):
		l2.append([j, l1[j]])
	l3 = [l2[0], l2[1]]
	for j in range(2, var2):
		while len(l3) >= 2:
			u = l3[-1][1] - l3[-2][1]
			d = l3[-1][0] - l3[-2][0]
			s1 = u / d
			u = l2[j][1] - l3[-1][1]
			d = l2[j][0] - l3[-1][0]
			s2 = u / d
			if s2 >= s1:
				l3 = l3[:-1]
			else:
				break
		l3.append(l2[j])
		out = max(out, l3[-1][0] - l3[-2][0])
	print(out)


for _ in range(int(input())):
	n = int(input())
	given = list(map(int, input().rstrip().split()))
	if n <= 2:
		print(1)
	else:
		A = []
		answer = 1
		for j in range(n):
			D = [j, given[j]]
			A.append(D)
		B = []
		B.append(A[0])
		B.append(A[1])
		lena = len(B)
		for i in range(2, n):
			while lena >= 2:
				S1 = (B[lena - 1][1] - B[lena - 2][1]) / (B[lena - 1][0] - B[lena - 2][0])
				S2 = (A[i][1] - B[lena - 1][1]) / (A[i][0] - B[lena - 1][0])
				if S1 <= S2:
					B.pop()
					lena -= 1
				else:
					break
			B.append(A[i])
			lena += 1
			answer = max(answer, B[lena - 1][0] - B[lena - 2][0])
		print(answer)


try:
	for i in range(int(input())):
		n = int(input())
		a = [int(i) for i in input().split()]
		if n <= 2:
			print(1)
		else:
			ans = -1
			newa = []
			for i in range(n):
				newa.append([i, a[i]])
			b = []
			b.append(newa[0])
			b.append(newa[1])
			l = len(b)
			for i in range(2, n):
				while len(b) >= 2:
					slope1 = (b[l - 1][1] - b[l - 2][1]) / (b[l - 1][0] - b[l - 2][0])
					slope2 = (newa[i][1] - b[l - 1][1]) / (newa[i][0] - b[l - 1][0])
					if slope2 >= slope1:
						b.pop()
						l -= 1
					else:
						break
				b.append(newa[i])
				l += 1
				ans = max(ans, b[l - 1][0] - b[l - 2][0])
			print(ans)
except:
	pass


import sys

def mi(s):
	return map(int, s.strip().split())

def lmi(s):
	return list(mi(s))

def tmi(s):
	return tuple(mi(s))

def mf(f, s):
	return map(f, s)

def lmf(f, s):
	return list(mf(f, s))

def js(lst):
	return ' '.join((str(d) for d in lst))

def jsns(lst):
	return ''.join((str(d) for d in lst))

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

def linesp():
	return line().split()

def iline():
	return int(line())

def mat(n):
	matr = []
	for _ in range(n):
		matr.append(linesp())
	return matr

def matns(n):
	mat = []
	for _ in range(n):
		mat.append([c for c in line()])
	return mat

def mati(n):
	mat = []
	for _ in range(n):
		mat.append(lmi(line()))
	return mat

def pmat(mat):
	for row in mat:
		print(js(row))
import math
import sys
import collections
import bisect
import string
import time

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

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

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

def convex_hull(points):
	points = sorted(set(points))
	if len(points) <= 1:
		return points

	def cross(o, a, b):
		return (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0])
	lower = []
	for p in points:
		while len(lower) >= 2 and cross(lower[-2], lower[-1], p) <= 0:
			lower.pop()
		lower.append(p)
	upper = []
	for p in reversed(points):
		while len(upper) >= 2 and cross(upper[-2], upper[-1], p) <= 0:
			upper.pop()
		upper.append(p)
	return lower[:-1] + upper[:-1]
for t in range(int(input())):
	n = int(input())
	arr = get_list()
	starting = [(1, 0)]
	for j in range(0, n, 1):
		starting.append((j + 1, arr[j]))
	starting.append((n, 0))
	solution = convex_hull(starting)
	solution.sort()
	ans = 0
	for i in range(2, len(solution) - 1):
		val = solution[i][0] - solution[i - 1][0]
		ans = max(ans, val)
	print(ans)


from sys import stdin, stdout
import math
import math

def ii():
	return int(stdin.readline())

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

def li():
	return list(mi())

def si():
	return stdin.readline()

def slope(p1, p2):
	return (p2[1] - p1[1]) / (p2[0] - p1[0])
for _ in range(ii()):
	n = ii()
	l1 = [(i + 1, v) for (i, v) in enumerate(li())]
	ans = 1
	stack = []
	stack.append(l1[0])
	stack.append(l1[1])
	for i in range(2, n):
		while len(stack) >= 2:
			if slope(l1[i], stack[-1]) >= slope(stack[-2], l1[i]):
				stack.pop()
			else:
				break
		stack.append(l1[i])
		ans = max(ans, abs(stack[-1][0] - stack[-2][0]))
	print(ans)


from bisect import bisect_left
from bisect import bisect_right

def I():
	return inp()

def II():
	return int(inp())

def FI():
	return float(inp())

def SI():
	return list(str(inp()))

def MI():
	return map(int, inp().split())

def LI():
	return list(MI())

def SLI():
	return sorted(LI())

def MF():
	return map(float, inp().split())

def LF():
	return list(MF())

def SLF():
	return sorted(LF())

def prefixSum(arr):
	for i in range(1, len(arr)):
		arr[i] = arr[i] + arr[i - 1]
	return arr

def isPowerOf2(x):
	return x and (not x & x - 1)

def power2(n):
	return len(str(bin(n & ~(n - 1))) - 1)

def sumn(n):
	return n * (n + 1) // 2

def sqsum(n):
	return n * (n + 1) * (2 * n + 1) // 6

def cusum(n):
	return sumn(n) ** 2

def result(n, a):
	list1 = []
	res = 1
	if n == 2:
		return 1
	else:
		list1.append(tuple((0, a[0])))
		list1.append(tuple((1, a[1])))
		for i in range(2, n):
			while len(list1) >= 2:
				x = (list1[len(list1) - 1][1] - list1[len(list1) - 2][1]) / (list1[len(list1) - 1][0] - list1[len(list1) - 2][0])
				y = (a[i] - list1[len(list1) - 1][1]) / (i - list1[len(list1) - 1][0])
				if x <= y:
					list1.pop()
				else:
					break
			list1.append(tuple((i, a[i])))
			if res < list1[len(list1) - 1][0] - list1[len(list1) - 2][0]:
				res = list1[len(list1) - 1][0] - list1[len(list1) - 2][0]
		return res
t = int(input())
for i in range(0, t):
	n = int(input())
	a = list(map(int, input().split()))[:n]
	print(result(n, a))


t = input()
for _ in range(int(t)):
	n = int(input())
	h = list(map(int, input().split()))
	for i in range(n):
		h[i] = [i, h[i]]
	if n <= 2:
		print(1)
	else:
		cnt = 1
		h2 = [h[0], h[1]]
		l = len(h2)
		for i in range(2, n):
			while len(h2) >= 2:
				s1 = (h2[l - 1][1] - h2[l - 2][1]) / (h2[l - 1][0] - h2[l - 2][0])
				s2 = (h[i][1] - h2[l - 1][1]) / (h[i][0] - h2[l - 1][0])
				if s2 >= s1:
					h2.pop()
					l -= 1
				else:
					break
			h2.append(h[i])
			l += 1
			cnt = max(cnt, h2[l - 1][0] - h2[l - 2][0])
		print(cnt)


def digbig(a, b):
	if a >= b:
		return a
	else:
		return b
t = int(input())
for jj in range(t):
	n = int(input())
	h = list(map(int, input().split()))
	if n <= 2:
		print(1)
	else:
		ans = 1
		a = []
		for j in range(n):
			a.append([j + 1, h[j]])
		b = [a[0]]
		b.append(a[1])
		initial_len = len(b)
		for i in range(2, n):
			while initial_len >= 2:
				y2 = b[initial_len - 1][1]
				y1 = b[initial_len - 2][1]
				diff_y = y2 - y1
				x2 = b[initial_len - 1][0]
				x1 = b[initial_len - 2][0]
				diff_x = x2 - x1
				slope1 = diff_y / diff_x
				yc = a[i][1]
				xc = a[i][0]
				diff_y_sec = yc - y2
				diff_x_sec = xc - x2
				slope2 = diff_y_sec / diff_x_sec
				if slope2 >= slope1:
					b.pop(-1)
					initial_len = initial_len - 1
				else:
					break
			b.append(a[i])
			initial_len = initial_len + 1
			ans = digbig(ans, b[initial_len - 1][0] - b[initial_len - 2][0])
		print(ans)


t = int(input())
while t:
	n = int(input())
	h = list(map(int, input().split()))
	ans = 1
	if n == 2:
		ans = 1
	else:
		dp = []
		dp.append([1, h[0]])
		dp.append([2, h[1]])
		size = len(dp)
		for i in range(2, n):
			while len(dp) >= 2:
				slope1 = (dp[size - 1][1] - dp[size - 2][1]) / (dp[size - 1][0] - dp[size - 2][0])
				slope2 = (h[i] - dp[size - 1][1]) / (i + 1 - dp[size - 1][0])
				if slope2 >= slope1:
					dp.pop()
					size -= 1
				else:
					break
			dp.append([i + 1, h[i]])
			size += 1
			ans = max(ans, dp[size - 1][0] - dp[size - 2][0])
	print(ans)
	t -= 1


def my_func():
	n = int(input())
	arr = list(map(int, input().split()))
	if n <= 2:
		print(1)
	else:
		res = 1
		a = []
		for i in range(n):
			a.append([i + 1, arr[i]])
		b = []
		b.append(a[0])
		b.append(a[1])
		l = len(b)
		for i in range(2, n):
			while l >= 2:
				x = (b[l - 1][1] - b[l - 2][1]) / (b[l - 1][0] - b[l - 2][0])
				y = (b[l - 1][1] - a[i][1]) / (b[l - 1][0] - a[i][0])
				if y >= x:
					b.pop()
					l -= 1
				else:
					break
			b.append(a[i])
			l += 1
			res = max(res, b[l - 1][0] - b[l - 2][0])
		print(res)
for _ in range(int(input())):
	my_func()


for _ in range(int(input())):
	n = int(input())
	stack = []
	arr = list(map(int, input().split()))
	p = [[i + 1, arr[i]] for i in range(n)]
	if n == 2:
		print(1)
		continue
	stack.append(p[0])
	stack.append(p[1])
	(ans, l) = (1, len(stack))
	for i in range(2, n):
		while len(stack) >= 2:
			s1 = (stack[-1][1] - stack[-2][1]) / (stack[-1][0] - stack[-2][0])
			s2 = (p[i][1] - stack[-1][1]) / (p[i][0] - stack[-1][0])
			if s1 <= s2:
				stack.pop()
			else:
				break
		stack.append(p[i])
		ans = max(ans, stack[-1][0] - stack[-2][0])
	print(ans)


import math

def lengthSquare(X, Y):
	xDiff = X[0] - Y[0]
	yDiff = X[1] - Y[1]
	return xDiff * xDiff + yDiff * yDiff

def findAngle(A, B, C):
	a2 = lengthSquare(B, C)
	b2 = lengthSquare(A, C)
	c2 = lengthSquare(A, B)
	a = math.sqrt(a2)
	b = math.sqrt(b2)
	c = math.sqrt(c2)
	betta = math.acos((a2 + c2 - b2) / (2 * a * c))
	betta = betta * 180 / math.pi
	return betta
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	if n == 2:
		print(1)
	else:
		tmp = [[1, a[0]], [2, a[1]]]
		res = 1
		s = len(tmp)
		for i in range(2, n):
			while len(tmp) >= 2:
				s1 = (tmp[-1][1] - tmp[-2][1]) / (tmp[-1][0] - tmp[-2][0])
				s2 = (a[i] - tmp[-1][1]) / (i + 1 - tmp[-1][0])
				if s1 <= s2:
					tmp.pop()
					s -= 1
				else:
					break
			tmp.append([i + 1, a[i]])
			s += 1
			res = max(res, tmp[-1][0] - tmp[-2][0])
		print(res)


import math
t = int(input())
for _ in range(t):
	n = int(input())
	h = list(map(int, input().split()))
	d1 = []
	cur = 0
	for i in range(n):
		if h[i] > cur:
			cur = h[i]
			d1.append((h[i], i))
	d2 = []
	cur = 0
	for i in range(n - 1, -1, -1):
		if h[i] > cur:
			cur = h[i]
			d2.append((h[i], i))
	ans = 1
	if len(d1) == len(d2) == 1 and n > 1:
		ans = n - 1
	else:
		m = max(h)
		ind1 = 0
		ind2 = 0
		for i in range(n):
			if h[i] == m:
				ind1 = i
				break
		for i in range(n - 1, -1, -1):
			if h[i] == m:
				ind2 = i
				break
		ans = max(ans, ind2 - ind1)
		if len(d1) > 1:
			stack = [d1[0], d1[1]]
			ans = max(ans, abs(stack[-1][1] - stack[-2][1]))
			for i in range(2, len(d1)):
				while len(stack) >= 2:
					slope1 = (stack[-1][0] - stack[-2][0]) / (stack[-1][1] - stack[-2][1])
					slope2 = (d1[i][0] - stack[-1][0]) / (d1[i][1] - stack[-1][1])
					if abs(slope1) <= abs(slope2):
						stack.pop()
					else:
						break
				stack.append(d1[i])
				ans = max(ans, abs(stack[-1][1] - stack[-2][1]))
		if len(d2) > 1:
			stack = [d2[0], d2[1]]
			ans = max(ans, abs(stack[-1][1] - stack[-2][1]))
			for i in range(2, len(d2)):
				while len(stack) >= 2:
					slope1 = (stack[-1][0] - stack[-2][0]) / (stack[-1][1] - stack[-2][1])
					slope2 = (d2[i][0] - stack[-1][0]) / (d2[i][1] - stack[-1][1])
					if abs(slope1) <= abs(slope2):
						stack.pop()
					else:
						break
				stack.append(d2[i])
				ans = max(ans, abs(stack[-1][1] - stack[-2][1]))
		print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	heights = list(map(int, input().split()))
	if n <= 2:
		print(1)
	else:
		max_diff = 1
		tupleList = [tup for tup in enumerate(heights)]
		stack = [tupleList[0], tupleList[1]]
		l = 2
		for j in range(2, n):
			while l >= 2:
				slope1 = (stack[l - 1][1] - stack[l - 2][1]) / (stack[l - 1][0] - stack[l - 2][0])
				slope2 = (tupleList[j][1] - stack[l - 1][1]) / (tupleList[j][0] - stack[l - 1][0])
				if slope2 >= slope1:
					stack.pop()
					l -= 1
				else:
					break
			stack.append(tupleList[j])
			l += 1
			max_diff = max(max_diff, stack[l - 1][0] - stack[l - 2][0])
		print(max_diff)


t = int(input())
for x in range(0, t):
	N = int(input())
	if N <= 2:
		print(1)
		temp = input()
		continue
	res = 1
	string = input().split(' ')
	li = []
	for y in range(0, len(string)):
		li.append([y, int(string[y])])
	li2 = [li[0], li[1]]
	length = len(li2)
	for i in range(2, N):
		while length >= 2:
			slp1 = (li2[length - 1][1] - li2[length - 2][1]) / (li2[length - 1][0] - li2[length - 2][0])
			slp2 = (li[i][1] - li2[length - 1][1]) / (li[i][0] - li2[length - 1][0])
			if slp2 >= slp1:
				li2.pop()
				length = length - 1
			else:
				break
		li2.append(li[i])
		length = length + 1
		res = max(res, li2[length - 1][0] - li2[length - 2][0])
	print(res)


for t in range(int(input())):
	n = int(input())
	sec = list(map(int, input().split()))
	if n <= 2:
		print(1)
	else:
		res = 1
		a = []
		for i in range(n):
			a.append([i, sec[i]])
		b = [a[0], a[1]]
		l = len(b)
		for i in range(2, n):
			while l >= 2:
				s1 = (b[l - 1][1] - b[l - 2][1]) / (b[l - 1][0] - b[l - 2][0])
				s2 = (a[i][1] - b[l - 1][1]) / (a[i][0] - b[l - 1][0])
				if s2 >= s1:
					b.pop()
					l -= 1
				else:
					break
			b.append(a[i])
			l += 1
			res = max(res, b[l - 1][0] - b[l - 2][0])
		print(res)


for _ in range(int(input())):
	n = int(input())
	H = [int(x) for x in input().split()]
	if n <= 2:
		print(1)
	else:
		ans = 1
		a = []
		for i in range(n):
			a.append([i, H[i]])
		b = [[0, a[0][1]], [1, a[1][1]]]
		l = 2
		for i in range(2, n):
			while l >= 2:
				slope1 = (b[l - 1][1] - b[l - 2][1]) / (b[l - 1][0] - b[l - 2][0])
				slope2 = (a[i][1] - b[l - 1][1]) / (a[i][0] - b[l - 1][0])
				if slope2 >= slope1:
					b.pop()
					l -= 1
				else:
					break
			b.append(a[i])
			l += 1
			ans = max(ans, b[l - 1][0] - b[l - 2][0])
		print(ans)


T = int(input())
for t in range(T):
	n = int(input())
	h = list(map(int, input().split()))
	if n <= 2:
		print(1)
		continue
	a = []
	for i in range(n):
		a.append([i, h[i]])
	b = [a[0], a[1]]
	l = len(b)
	ans = 1
	for i in range(2, n):
		while l >= 2:
			slope1 = (b[l - 1][1] - b[l - 2][1]) / (b[l - 1][0] - b[l - 2][0])
			slope2 = (a[i][1] - b[l - 1][1]) / (a[i][0] - b[l - 1][0])
			if slope2 >= slope1:
				b.pop()
				l -= 1
			else:
				break
		b.append(a[i])
		l += 1
		ans = max(ans, b[l - 1][0] - b[l - 2][0])
	print(ans)


for _ in range(int(input())):
	n = int(input())
	h = list(map(int, input().split()))
	indx = [(i, i + 1) for i in range(n - 1)]
	done = False
	if n == 2:
		print(1)
		continue
	while not done:
		done = True
		new_indx = []
		i = 0
		while i < len(indx) - 1:
			(p1, p2) = indx[i]
			(_, p3) = indx[i + 1]
			m1 = (h[p2] - h[p1]) / (p2 - p1)
			m2 = (h[p3] - h[p2]) / (p3 - p2)
			if m1 <= m2:
				new_indx.append((p1, p3))
				done = False
				i += 1
			else:
				new_indx.append(indx[i])
			if i + 2 == len(indx):
				new_indx.append(indx[i + 1])
			i += 1
		indx = new_indx
		if len(indx) == 1:
			done = True
	answer = [i[1] - i[0] for i in indx]
	print(max(answer))


for _ in range(int(input())):
	n = int(input())
	d = list(map(int, input().rstrip().split()))
	if n <= 2:
		print(1)
	else:
		ans = 1
		a = []
		for i in range(n):
			c = [i, d[i]]
			a.append(c)
		b = []
		b.append(a[0])
		b.append(a[1])
		len1 = len(b)
		for i in range(2, n):
			while len1 >= 2:
				slope1 = (b[len1 - 1][1] - b[len1 - 2][1]) / (b[len1 - 1][0] - b[len1 - 2][0])
				slope2 = (a[i][1] - b[len1 - 1][1]) / (a[i][0] - b[len1 - 1][0])
				if slope2 >= slope1:
					b.pop()
					len1 = len1 - 1
				else:
					break
			b.append(a[i])
			len1 = len1 + 1
			ans = max(ans, b[len1 - 1][0] - b[len1 - 2][0])
		print(ans)


t = int(input())
for i in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	if n <= 2:
		print(1)
		continue
	ans = 1
	a = []
	for j in range(n):
		a.append([j, arr[j]])
	b = [a[0], a[1]]
	for j in range(2, n):
		while len(b) >= 2:
			nr = b[-1][1] - b[-2][1]
			dr = b[-1][0] - b[-2][0]
			slope1 = nr / dr
			nr = a[j][1] - b[-1][1]
			dr = a[j][0] - b[-1][0]
			slope2 = nr / dr
			if slope2 >= slope1:
				b = b[:-1]
			else:
				break
		b.append(a[j])
		ans = max(ans, b[-1][0] - b[-2][0])
	print(ans)


def process(l):
	if len(l) == 2:
		return 1
	n = len(l)
	a = [0]
	c = 0
	for j in range(1, n):
		if l[j] >= l[a[-1]]:
			c = 10000000
			p = len(a)
			for i in range(p):
				slope = (l[j] - l[a[p - i - 1]]) / (j - a[p - i - 1])
				if slope <= c:
					a = a[:p - i] + [j]
					c = slope
	ans = 1
	for i in range(len(a) - 1):
		if a[i + 1] - a[i] > ans:
			ans = a[i + 1] - a[i]
	return ans
no = int(input())
for it in range(no):
	n = int(input())
	a = list(map(int, input().split()))
	if n < 100000:
		slope = -1000000000000000
		dist = 1
		next = 0
		i = 0
		while i < n - 1:
			slope = -1000000000000000
			for j in range(i + 1, n):
				if (a[j] - a[i]) / (j - i) >= slope:
					next = j
					slope = (a[j] - a[i]) / (j - i)
					dist = max(dist, j - i)
			i = next
		print(dist)
	else:
		print(max(process(a), process(a[::-1])))


n = int(input())
for m in range(n):
	l = int(input())
	flag = False
	li = [int(x) for x in input().split()]
	if len(li) <= 2:
		print(1)
		flag = True
	if flag == False:
		d = []
		for i in range(len(li)):
			d.append([i + 1, li[i]])
		b = d[:2]
		q = 2
		ans = 0
		for i in range(2, len(li)):
			while len(b) >= 2:
				prevSlope = (b[q - 1][1] - b[q - 2][1]) / (b[q - 1][0] - b[q - 2][0])
				newSlope = (d[i][1] - b[q - 1][1]) / (d[i][0] - b[q - 1][0])
				if newSlope >= prevSlope:
					b.pop()
					q -= 1
				else:
					break
			b.append(d[i])
			q += 1
			ans = max(ans, b[q - 1][0] - b[q - 2][0])
		print(ans)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	cord = [(1, l[0]), (2, l[1])]
	ln_cord = 2
	mx = 1
	for i in range(2, n):
		while ln_cord >= 2:
			sl1 = (cord[ln_cord - 1][1] - cord[ln_cord - 2][1]) / (cord[ln_cord - 1][0] - cord[ln_cord - 2][0])
			sl2 = (cord[ln_cord - 1][1] - l[i]) / (cord[ln_cord - 1][0] - (i + 1))
			if sl1 <= sl2:
				cord = cord[:ln_cord - 1]
				ln_cord = ln_cord - 1
			else:
				break
		cord.append((i + 1, l[i]))
		ln_cord += 1
		mx = max(mx, cord[ln_cord - 1][0] - cord[ln_cord - 2][0])
	print(mx)


T = int(input())
sol = []

def pivot(L, N, T, S):
	if S == 2:
		return ([0], T[1] - T[0])
	x = 0
	y = 1
	t = []
	s = 0
	while y <= S - 2:
		if (L[T[y]] - L[T[x]]) / (T[y] - T[x]) <= (L[T[y + 1]] - L[T[y]]) / (T[y + 1] - T[y]):
			y += 1
			continue
		else:
			t.append(T[y])
			x = y
			y += 1
			s += 1
	t = [0] + t + [N - 1]
	s += 2
	if t == T:
		return (t, s)
	else:
		return pivot(L, N, t, s)
for i in range(T):
	N = int(input())
	L = list(map(int, input().split()))
	if N == 2:
		sol.append(1)
		continue
	else:
		pass
	dummy = [i for i in range(N)]
	(T, S) = pivot(L, N, dummy, N)
	if len(T) == 1:
		sol.append(S)
		continue
	elif S == N:
		sol.append(1)
		continue
	elif S == N - 1:
		sol.append(2)
		continue
	elif S == 3:
		sol.append(max(T[1] - T[0], T[2] - T[1]))
		continue
	else:
		pass
	ans = 0
	for j in range(0, S - 1):
		z = -float('inf')
		for k in range(j + 1, S):
			if (L[T[k]] - L[T[j]]) / (T[k] - T[j]) >= z:
				z = (L[T[k]] - L[T[j]]) / (T[k] - T[j])
				ans = max(ans, T[k] - T[j])
				continue
			else:
				continue
	sol.append(ans)
for i in sol:
	print(i)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	if n == 2 or n == 1:
		print(1)
		continue
	b = []
	for i in range(n):
		b.append([i, a[i]])
	c = []
	c.append(b[0])
	c.append(b[1])
	sol = 1
	ind = len(c)
	for i in range(2, n):
		while len(c) >= 2:
			s1 = (c[ind - 1][1] - c[ind - 2][1]) / (c[ind - 1][0] - c[ind - 2][0])
			s2 = (b[i][1] - c[ind - 1][1]) / (b[i][0] - c[ind - 1][0])
			if s1 <= s2:
				c.pop()
				ind = ind - 1
			else:
				break
		c.append(b[i])
		ind += 1
		sol = max(sol, c[ind - 1][0] - c[ind - 2][0])
	print(sol)


for _ in range(int(input())):
	n = int(input())
	mp = list(map(int, input().split()))
	step = [0, 1]
	if n == 2:
		print(mp[1] - mp[0])
		continue
	for i in range(2, n):
		if (mp[step[-1]] - mp[step[-2]]) / (step[-1] - step[-2]) <= (mp[i] - mp[step[-2]]) / (i - step[-2]):
			while len(step) > 1 and (mp[step[-1]] - mp[step[-2]]) / (step[-1] - step[-2]) <= (mp[i] - mp[step[-2]]) / (i - step[-2]):
				step.pop()
		step.append(i)
	ans = 1
	for i in range(len(step) - 1):
		ans = max(ans, step[i + 1] - step[i])
	print(ans)


def maximum(num1, num2):
	if num1 > num2:
		return num1
	else:
		return num2
t = int(input())
for _ in range(t):
	comp_list = list()
	sub_list = list()
	n = input()
	n = int(n)
	list1 = [int(x) for x in input().split()]
	if n == 2:
		print('1')
		continue
	for l in range(n):
		comp_list.append([l, list1[l]])
	sub_list = comp_list[:2]
	output = 1
	length = 2
	for l in range(2, n, 1):
		while length >= 2:
			slope2 = (comp_list[l][1] - sub_list[length - 1][1]) / (comp_list[l][0] - sub_list[length - 1][0])
			slope1 = (sub_list[length - 1][1] - sub_list[length - 2][1]) / (sub_list[length - 1][0] - sub_list[length - 2][0])
			if slope1 > slope2:
				break
			else:
				sub_list.pop(-1)
				length = len(sub_list)
		sub_list.append(comp_list[l])
		length = len(sub_list)
		output = maximum(output, sub_list[length - 1][0] - sub_list[length - 2][0])
	print(output)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	if n == 2:
		print('1')
	else:
		max1 = 1
		a = []
		for i in range(n):
			a.append([i + 1, l[i]])
		b = [a[0], a[1]]
		ln = len(b)
		for i in range(2, n):
			while ln >= 2:
				slp1 = (b[ln - 1][1] - b[ln - 2][1]) / (b[ln - 1][0] - b[ln - 2][0])
				slp2 = (a[i][1] - b[ln - 1][1]) / (a[i][0] - b[ln - 1][0])
				if slp2 >= slp1:
					b.pop()
					ln -= 1
				else:
					break
			b.append(a[i])
			ln += 1
			max1 = max(max1, b[ln - 1][0] - b[ln - 2][0])
		print(max1)


t = int(input())
while t:
	n = int(input())
	height = list(map(int, input().split()))
	section = [0] * n
	for i in range(n):
		section[i] = [i, height[i]]
	if n == 2:
		print(1)
		t -= 1
		continue
	stack = [section[0], section[1]]
	stack_size = len(stack)
	res = 1
	for i in range(2, n):
		while stack_size >= 2:
			current_slope = (section[i][1] - stack[stack_size - 1][1]) / (section[i][0] - stack[stack_size - 1][0])
			prev_largest_slope = (stack[stack_size - 1][1] - stack[stack_size - 2][1]) / (stack[stack_size - 1][0] - stack[stack_size - 2][0])
			if current_slope >= prev_largest_slope:
				stack.pop()
				stack_size -= 1
			else:
				break
		stack.append(section[i])
		stack_size += 1
		current_max_dist = stack[stack_size - 1][0] - stack[stack_size - 2][0]
		res = max(res, current_max_dist)
	print(res)
	t -= 1


t = int(input())
for _ in range(t):
	n = int(input())
	li = [int(x) for x in input().split()]
	list1 = list()
	list2 = list()
	if n <= 2:
		print('1')
		continue
	answer = 1
	for i in range(n):
		list1.append([i, li[i]])
	list2.append(list1[0])
	list2.append(list1[1])
	l = 2
	for i in range(2, n, 1):
		while l >= 2:
			slope1 = (list2[l - 1][1] - list2[l - 2][1]) / (list2[l - 1][0] - list2[l - 2][0])
			slope2 = (list1[i][1] - list2[l - 1][1]) / (list1[i][0] - list2[l - 1][0])
			if slope2 >= slope1:
				list2.pop()
				l = l - 1
			else:
				break
		list2.append(list1[i])
		l = l + 1
		answer = max(answer, list2[l - 1][0] - list2[l - 2][0])
	print(answer)


def fun(l, n):
	if n == 2:
		print(1)
	else:
		ans = 1
		a = []
		for i in range(len(l)):
			a.append([i, l[i]])
		a1 = []
		a1.append(a[0])
		a1.append(a[1])
		l = len(a1)
		for i in range(2, n):
			while len(a1) >= 2:
				slope1 = (a1[l - 1][1] - a1[l - 2][1]) / (a1[l - 1][0] - a1[l - 2][0])
				slope2 = (a[i][1] - a1[l - 1][1]) / (a[i][0] - a1[l - 1][0])
				if slope1 <= slope2:
					a1.pop()
					l -= 1
				else:
					break
			a1.append(a[i])
			l += 1
			ans = max(ans, a1[l - 1][0] - a1[l - 2][0])
		print(ans)
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	fun(l, n)


for _ in range(0, int(input())):
	n = int(input())
	h = [int(x) for x in input().split()]
	if n <= 2:
		print('1')
	else:
		ans = 1
		a = []
		for i in range(n):
			a.append([i, h[i]])
		b = [[0, a[0][1]], [1, a[1][1]]]
		for i in range(2, n):
			lenght = len(b)
			while lenght >= 2:
				slope1 = (b[lenght - 1][1] - b[lenght - 2][1]) / (b[lenght - 1][0] - b[lenght - 2][0])
				slope2 = (a[i][1] - b[lenght - 1][1]) / (a[i][0] - b[lenght - 1][0])
				if slope2 >= slope1:
					b.pop()
					lenght = lenght - 1
				else:
					break
			b.append(a[i])
			lenght = lenght + 1
			ans = max(ans, b[lenght - 1][0] - b[lenght - 2][0])
		print(ans)


def solve():
	n = inp()
	h = inl()
	if n <= 2:
		print(1)
		return
	a = []
	for i in range(n):
		a.append([i, h[i]])
	b = [a[0], a[1]]
	l = len(b)
	ans = 1
	for i in range(2, n):
		while len(b) >= 2:
			slp1 = (b[l - 1][1] - b[l - 2][1]) / (b[l - 1][0] - b[l - 2][0])
			slp2 = (a[i][1] - b[l - 1][1]) / (a[i][0] - b[l - 1][0])
			if slp2 >= slp1:
				b.pop()
				l -= 1
			else:
				break
		b.append(a[i])
		l += 1
		ans = max(ans, b[l - 1][0] - b[l - 2][0])
	print(ans)

def inp():
	return int(input())

def inl():
	return [int(i) for i in input().split()]
t = 1
t = inp()
while t:
	solve()
	t -= 1


for _ in range(int(input())):
	n = int(input())
	H = list(map(int, input().split()))
	if n == 2:
		print(1)
		continue
	if n <= 5 * 10 ** 5:
		temp = []
		temp.append((0, H[0]))
		temp.append((1, H[1]))
		ans = 1
		for i in range(2, n):
			tlen = len(temp)
			while tlen >= 2:
				A = (temp[tlen - 1][1] - temp[tlen - 2][1]) / (temp[tlen - 1][0] - temp[tlen - 2][0])
				B = (H[i] - temp[tlen - 1][1]) / (i - temp[tlen - 1][0])
				if A <= B:
					temp.pop()
					tlen -= 1
				else:
					break
			temp.append((i, H[i]))
			tlen += 1
			if ans < temp[tlen - 1][0] - temp[tlen - 2][0]:
				ans = temp[tlen - 1][0] - temp[tlen - 2][0]
		print(ans)


for _ in range(int(input())):
	n = int(input())
	h = [int(x) for x in input().split()]
	p = []
	for i in range(n):
		p.append([i, h[i]])
	if n == 2:
		print(1)
		continue
	maxd = 1
	t = []
	t.append(p[0])
	t.append(p[1])
	m = len(t)
	for i in range(2, n):
		while len(t) >= 2:
			m1 = (t[m - 1][1] - t[m - 2][1]) / (t[m - 1][0] - t[m - 2][0])
			m2 = (p[i][1] - t[m - 1][1]) / (p[i][0] - t[m - 1][0])
			if m1 <= m2:
				t = t[:-1]
				m -= 1
			else:
				break
		t.append(p[i])
		m += 1
		maxd = max(maxd, t[m - 1][0] - t[m - 2][0])
	print(maxd)


for tests in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	vh = []
	for i in range(n):
		vh.append([i + 1, a[i]])
	if n == 2:
		print(1)
	else:
		angle = [vh[0], vh[1]]
		(it, ans) = (2, 1)
		for i in range(2, n):
			while len(angle) > 1:
				y1 = angle[it - 1][1] - angle[it - 2][1]
				x1 = angle[it - 1][0] - angle[it - 2][0]
				y2 = vh[i][1] - angle[it - 1][1]
				x2 = vh[i][0] - angle[it - 1][0]
				first = y1 / x1
				second = y2 / x2
				if first <= second:
					it -= 1
					angle.pop()
				else:
					break
			angle.append(vh[i])
			it += 1
			ans = max(ans, angle[it - 1][0] - angle[it - 2][0])
		print(ans)


from math import *
tf = float('inf')
for y in range(int(input())):
	n = int(input())
	lst = list(map(int, input().split()))
	if n == 2:
		print('1')
		continue
	for i in range(n):
		lst[i] = [i + 1, lst[i]]
	lst2 = [lst[0], lst[1]]
	ans = 1
	mn = 2
	for i in range(2, n):
		while mn >= 2:
			ans1 = (lst2[-1][1] - lst2[-2][1]) / (lst2[-1][0] - lst2[-2][0])
			ans2 = (lst[i][1] - lst2[-1][1]) / (lst[i][0] - lst2[-1][0])
			if ans1 <= ans2:
				lst2.pop()
				mn -= 1
			else:
				break
		lst2.append(lst[i])
		mn += 1
		ans = max(ans, lst2[mn - 1][0] - lst2[mn - 2][0])
	print(ans)


try:
	t = int(input())
	while t:
		n = int(input())
		arr = list(map(int, input().split()))
		if len(arr) <= 2:
			print(1)
			continue
		ans = 1
		(p, st) = ([], [])
		for i in range(len(arr)):
			p.append([i + 1, arr[i]])
		st.append(p[0])
		st.append(p[1])
		n = len(st)
		for i in range(2, len(arr)):
			while n >= 2:
				s1 = (st[n - 1][1] - st[n - 2][1]) / (st[n - 1][0] - st[n - 2][0])
				s2 = (p[i][1] - st[n - 1][1]) / (p[i][0] - st[n - 1][0])
				if s1 <= s2:
					st.pop()
					n -= 1
				else:
					break
			st.append(p[i])
			n += 1
			ans = max(ans, st[n - 1][0] - st[n - 2][0])
		print(ans)
		t -= 1
except:
	pass


def hull(xs):
	ret = []
	for (i, x) in enumerate(xs):
		while len(ret) >= 2:
			(j, k) = (ret[-1], ret[-2])
			(xj, xk) = (xs[j], xs[k])
			if (xk - xj) * (i - j) < (k - j) * (x - xj):
				break
			ret.pop()
		ret.append(i)
	return ret
import sys
ff = sys.stdin
t = int(ff.readline()[:-1])
for i in range(t):
	n = int(ff.readline()[:-1])
	x = list(map(int, ff.readline().split()))
	h = hull(x)
	print(max(map(lambda z: abs(z[1] - z[0]), zip(h, h[1:]))))


for t in range(int(input())):
	n = int(input())
	h = [int(x) for x in input().split()]
	p = [(i + 1, v) for (i, v) in enumerate(h)]
	st = []
	if n == 2:
		print(1)
		continue
	st.extend([p[0], p[1]])
	sol = 1
	s = len(st)
	for i in range(2, n):
		while len(st) >= 2:
			s1 = (st[s - 1][1] - st[s - 2][1]) / (st[s - 1][0] - st[s - 2][0])
			s2 = (p[i][1] - st[s - 1][1]) / (p[i][0] - st[s - 1][0])
			if s1 <= s2:
				st.pop()
				s -= 1
			else:
				break
		st.append(p[i])
		s += 1
		sol = max(sol, st[s - 1][0] - st[s - 2][0])
	print(sol)


try:
	for _ in range(int(input())):
		n = int(input())
		h = list(map(int, input().split()[:n]))
		ans = 1
		if n > 2:
			slist = [(1, h[0]), (2, h[1])]
			size = len(slist)
			for i in range(2, n):
				while len(slist) >= 2:
					pslope = (slist[-1][1] - slist[-2][1]) / (slist[-1][0] - slist[-2][0])
					nslope = (h[i] - slist[-1][1]) / (i + 1 - slist[-1][0])
					if pslope <= nslope:
						slist.pop(-1)
						size -= 1
					else:
						break
				slist.append((i + 1, h[i]))
				size += 1
				ans = max(ans, slist[-1][0] - slist[-2][0])
			print(ans)
		else:
			print(ans)
except:
	pass


def get_slope(p1, p2):
	if p1[0] == p2[0]:
		return float('inf')
	else:
		return 1.0 * (p1[1] - p2[1]) / (p1[0] - p2[0])

def get_cross_product(p1, p2, p3):
	return (p2[0] - p1[0]) * (p3[1] - p1[1]) - (p2[1] - p1[1]) * (p3[0] - p1[0])
t_n = int(input())
for i in range(t_n):
	n_1 = int(input())
	lis = list(map(int, input().split()))
	points = []
	for kk in range(1, len(lis) + 1):
		kl = []
		kl.append(kk)
		kl.append(lis[kk - 1])
		points.append(kl)
	hull = []
	start = points.pop(0)
	hull = [start]
	for po in points:
		hull.append(po)
		while len(hull) > 2 and get_cross_product(hull[-3], hull[-2], hull[-1]) >= 0:
			hull.pop(-2)
	lis_1 = []
	for ind in range(len(hull) - 1):
		lis_1.append(hull[ind + 1][0] - hull[ind][0])
	print(max(lis_1))