Chef has a garden of size N \times N. The garden is divided into N^{2} squares of size 1\times 1 each.

Chef has plants in some unit squares of the garden, because of which, that part looks *green*.  
Formally, for the i^{th} row (0 ≤ i < N), Chef has plants in all the columns from A_{i} to B_{i}  (both inclusive) where 0 ≤ A_{i} ≤ B_{i} < N.

Help Chef find the length of the side of the largest square that is *green*.

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

- The first line contains an integer N, the size of the garden. 
- The next N lines contain two space-separated integers A_{i} and B_{i}, representing that plants are present in all the columns from A_{i} to B_{i} (both inclusive) of the i^{th} row.

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

Output a single integer denoting the length of the side of the largest square that is *green*. In other words, output the length of the side of the square with maximum size, inside which all unit squares have plants.

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

$1 ≤N ≤10^{6}$
$0 ≤A_{i} ≤B_{i} < N$

----- Sample Input 1 ------ 
3
1 1
0 2
1 2

----- Sample Output 1 ------ 
2
----- explanation 1 ------ 

----- Sample Input 2 ------ 
8
2 4
2 4
1 4
0 7
0 3
1 2
1 2
1 1
----- Sample Output 2 ------ 
3

----- explanation 2 ------ 
Sample Explanation $1$: The garden looks like:

.png)

The largest green square has vertices $(1,1), (1,2), (2,2), (2,1)$. Thus, the length of the side of the largest *green* square is $2$.

Sample Explanation $2$: The garden looks like:

.png)

One of the largest green squares has vertices $(0,2), (0,4), (2, 4), (2, 2)$. Thus, the length of the side of the largest *green* square is $3$.  
There may be other squares with same size but it can be proven that no square with length more than $3$ is green.

Source: codechef | Difficulty: HARD
Tags: Sorting

Range queries

Segment trees revisited

Complete search

Data structures


Solutions:
from collections import deque
n = int(input())
q1 = deque()
res = 1

def helper(left1, right1, left2, right2):
	(temp1, temp2) = (max(left1, left2), min(right1, right2))
	if temp1 > right1 or temp1 > right2 or temp2 < left1 or (temp2 < left2):
		return None
	return (temp1, temp2)
for i in range(n):
	(left, right) = map(int, input().split())
	q2 = deque()
	while q1 and (q1[0][0][0] < left or q1[0][0][1] > right):
		top = q1.pop()
		(temp1, temp2) = top[0]
		width = top[0][1] - top[0][0] + 1
		height = i - 1 - top[1] + 1
		res = max(res, min(width, height))
		values = helper(left, right, temp1, temp2)
		if eval is not None:
			q2.append((values, top[1]))
	while q2:
		top = q2.pop()
		if top[0][1] - top[0][0] + 1 > res:
			q1.append(top)
	if not q1 or not (q1[-1][0][0] == left and q1[-1][0][1] == right):
		if right - left + 1 > res:
			q1.append(((left, right), i))
while q1:
	top = q1.pop()
	(temp1, temp2) = top[0]
	(height, width) = (n - top[1], temp2 - temp1 + 1)
	res = max(res, min(height, width))
print(res)


from collections import deque
rows = int(input())
stk = deque()
ans = 1

def overlap(l1, r1, l2, r2):
	(x, y) = (max(l1, l2), min(r1, r2))
	if x > r1 or x > r2 or y < l1 or (y < l2):
		return None
	return (x, y)
for j in range(rows):
	(lt, rt) = map(int, input().split())
	stkb = deque()
	while stk and (stk[-1][0][0] < lt or stk[-1][0][1] > rt):
		top = stk.pop()
		(x, y) = top[0]
		width = top[0][1] - top[0][0] + 1
		height = j - 1 - top[1] + 1
		ans = max(ans, min(width, height))
		eval = overlap(lt, rt, x, y)
		if eval is not None:
			stkb.append((eval, top[1]))
	while stkb:
		top = stkb.pop()
		if top[0][1] - top[0][0] + 1 > ans:
			stk.append(top)
	if not stk or not (stk[-1][0][0] == lt and stk[-1][0][1] == rt):
		if rt - lt + 1 > ans:
			stk.append(((lt, rt), j))
while stk:
	top = stk.pop()
	(x, y) = top[0]
	(height, width) = (rows - top[1], y - x + 1)
	ans = max(ans, min(height, width))
print(ans)