the-old-monk

Big Chandan is a dire lover of Biryani, especially Old Monk's Biryani. Today, he went over to have some of it. To his surprise, the waiter turns out be to be a coding geek and refuses to serves him unless Chandu solves his two- arrays problem, stated as:  

Given two non-increasing array of integers A,B  i.e A[i] ≥ A[i+1] and B[i] ≥ B[i+1] and for all i, 0 ≤ i < n-1.  

The monkiness of two numbers is given by: M (A[i],B[j]) = j - i
 , if j ≥i and B[j] ≥ A[i], or 0 otherwise. 

Find the monkiness of the two arrays, that is given by: M (A,B)=  max (M(A[i],B[j])) for 0≤ i, j< n-1.

Input Format:
The first line contains an integer, tc, denoting the number of test cases. The next line contains an integer, n, denoting the size of the two arrays. The size of both the arrays will be equal. After that line, the next line contains n integers denoting the numbers in the array A, and in the next line, there will be n numbers denoting the numbers in the array B.

Output format:
Print the monkiness of the two arrays.

Constraints:
1 ≤ Test Cases ≤ 50
1 ≤ N ≤ 10^5
1 ≤ Ai, Bi ≤ 10^12

SAMPLE INPUT
2
9
7 7 3 3 3 2 2 2 1
8 8 7 7 5 5 4 3 2
6
6 5 4 4 4 4
2 2 2 2 2 2

SAMPLE OUTPUT
5
0

Explanation

In the first case, we can see that 3 in the second array is the number which is equal to the 3 in the first array, and the difference between their positions is 5. So, the answer is 5.

Source: hackerearth | Difficulty: EASY
Tags: Sorting


Solutions:
#Salman Lari :)

def binsearch(B,item):
	#if item>max(B):
		#return i
	if B[len(B)-1]==item:
		return len(B)-1

	left=0
	right=len(B)-1
	#ans=0
	
	while right-left>1:
		mid=left+(right-left)/2
		if B[mid]>=item:
			#ans=mid
			#if mid==len(B)-1:
			#   break
			left=mid
		else:
			right=mid
	return left

tc=int(input())
for e in range(tc):
	n=int(input())
	A=[int(i) for i in input().split()]
	B=[int(i) for i in input().split()]

	#print A

	minA, maxA, minB, maxB= min(A), max(A), min(B), max(B)

	if maxB < minA:
		print(0)
		continue
	if minB >= maxA:
		print(n-1)
		continue
	mx=-1
	#m=(n-1)/2
	i=0
	while i<=n-1:
		j=binsearch(B,A[i])
		#print "i="+str(i)+" "+"j="+str(j)
		if j-i >= mx:
			mx = j-i
		i+=1
	print(mx)


def lastoccurrence(value,b,left,right):
	while((right-left)>1):
		mid=left+(right-left)/2
		if b[mid] >= value:
			left=mid
		else:
			right=mid
	return left        
tc=int(input())
for i in range(0,tc):
	n=int(input())
	a=list(map(int,input().split()))
	b=list(map(int,input().split()))
	maximum=0
	for i in range(0,n):
		if (a[i-1]==a[i]) and i!=0:
			continue
		else:
			value=a[i]
			right=lastoccurrence(value,b,0,n)
		
		if((right-i)>maximum):
			maximum=right-i
	print(maximum);


def monkiness(i,a,b,n):
	l=i
	u=n-1
	pos=i
	while l<=u:
		mid=(l+u)/2
		if b[mid]>=a[i]:
			pos=mid
			l=mid+1
		else:
			u=mid-1
	return pos-i
	
for _ in range(int(input())):
	n=int(input())
	a=list(map(int,input().split()))
	b=list(map(int,input().split()))
	masans=[0]
	for i in range(n):
		masans.append(monkiness(i,a,b,n))
	print(max(masans))


tc=int(input())
for k in range(tc):
	n=int(input())
	arr1=list(map(int,input().split()))
	arr2=list(map(int,input().split()))
	maxi=0
	for i in range(n):
		low=i+1
		high=n-1
		p=0
		while(low<=high):
			mid=(low+high)/2
			if(arr2[mid]>=arr1[i]):
				low=mid+1
				p=mid
						
			else:
				high=mid-1
		maxi=max(maxi,p-i)
	print(maxi)


def b_sr(l, i, lo=0, hi=None):
	if lo<0:
	   raise ValueError('lo must not be non-negative')
	if hi is None:
		hi = len(l)
	while lo<hi:
		mid=(lo+hi)//2
		# print mid
		#if l[mid]==i:return mid
		if i>l[mid]:hi = mid
		else:lo=mid+1
	return lo

def getM(A,B,size):
	max = 0
	for i in range(0,size):
		# for j in xrange(0,size):
		if B[i]>=A[i]:
			new_m = b_sr(B,A[i])-(i+1)
			if max < new_m:
				max = new_m
		else:
			pass
	print(max)
	
N = eval(input())
def get_A_B():
	AS = eval(input())
	A = list(map(int, input().split()))
	B = list(map(int, input().split()))
	return (A,B,AS)
	
for n in range(0,N):
	A,B,AS = get_A_B()
	getM(A,B,AS)
	
	
		 


def modBinSearch(array,start,end,value):
	if start<=end:
		#print 'enters'
		middle = (start+end)/2
		if array[middle]>value:
			return modBinSearch(array,middle+1,end,value)
		elif array[middle]<value:
			return modBinSearch(array,start,middle-1,value)
		else:
			while(middle==0 or array[middle-1]==value):
				#print 'happens'
				middle-=1
			
			return max(middle,0)
			
	else:
		return -1
for cases in range(eval(input())):
	n=eval(input())
	first=list(map(int,input().split(" ")))
	second=list(map(int,input().split(" ")))
	maxval=0
	p=0
	q=0
	cur_max=0
	for j in range(n):
		pos=-1
		start=0
		end=n-1
		while start<=end:
			middle=(start+end)/2
			if second[middle]>=first[j]:
				pos=middle
				start = middle+1
			else:
				end = middle-1
		cur_max=max(cur_max,pos-j)
		#print cur_max
	print(cur_max)
				
			


def findMonk(A,B,n):
	curmax=0 
	for i in range(n):
		low=0
		high=n-1
		pos=-1
		while(low<=high):
			mid=(low+high)//2
			if(B[mid]>A[i]):
				pos = mid
				low = mid+1
				
			elif(B[mid]==A[i]):
				pos = mid
				low = mid+1
				
			else:
				high = mid-1
				
		diff = pos-i    
		curmax = max(curmax,diff)       
	
	return curmax


if __name__ == "__main__":
	testcases = eval(input())
	
	for caseNr in range(1, testcases+1):
		N = int(input())
		Aarray = list(map(int,input().split()))     
		Barray = list(map(int,input().split()))         
		print(findMonk(Aarray,Barray,N))


tc = int(input())

def firstOccur(arr, left, right, item):
	mid = 0
	while(right - left > 1):
		mid = left + (right - left)/2
		if(item < arr[mid]):
			left = mid
		else:
			right = mid

	return right

for k in range(0, tc):
	size = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))

	max =  0
	i = 0
	for j in range(i, size):
		i = firstOccur(a, -1, size-1, b[j])
		if(i != -1 and j-i > max):
			max = j-i

	print(max)


from bisect import bisect
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))[::-1]
	b = list(map(int, input().split()))[::-1]
	c = []
	for i in range(n):
		x = bisect(a, b[i])
		if x > 0:
			c.append(x - i-1)
	if len(c):
		print(max(c))
	else:
		print(0)
		


'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
tc = int(input())
while tc>0:
	tc = tc - 1
	curMax = 0
	n = int(input())
	x = list(map(int, input().split()))
	y = list(map(int, input().split()))
	for i in range(n):
		low, high, pos = 0, n - 1, -1
		while low<=high:
			 mid = (low + high) / 2
			 if y[mid] >= x[i]:
				 pos = mid
				 low = mid + 1
			 else:
				 high = mid - 1
		curMax = max (curMax, pos - i)
	print(curMax)


def solve(xs, ys):
	last = None
	best = 0
	for j, y in reversed(list(enumerate(ys))):
		if y == last: continue
		found = j
		start = 0
		end = len(xs) - 1
		while start <= end:
			mid = (start + end) / 2
			if y < xs[mid]: start = mid + 1
			else:
				found = min(found, mid)
				end = mid - 1
		best = max(best, j - found)
	return best
		
if __name__ == '__main__':
	for _ in range(int(input())):
		_ = input()
		xs = list(map(int, input().split()))
		ys = list(map(int, input().split()))
		print(solve(xs, ys))


tc = int(input())
while tc>0:
	tc = tc - 1
	curMax = 0
	n = int(input())
	x = list(map(int, input().split()))
	y = list(map(int, input().split()))
	for i in range(n):
		low, high, pos = 0, n - 1, -1
		while low<=high:
			 mid = (low + high) / 2
			 if y[mid] >= x[i]:
				 pos = mid
				 low = mid + 1
			 else:
				 high = mid - 1
		curMax = max (curMax, pos - i)
	print(curMax)



'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''

def split_arr(ar, br, N):
	maximus = float('-inf')
	res = 0
	# O(NlgN)
	for i in range(N):
		a_num = ar[i]
		lo, hi = 0, N-1
		while lo <= hi:
			mid = (lo+hi)/2
			b_num = br[mid]
			if b_num >= a_num:
				res = mid - i
				if res > maximus:
					maximus = res
				lo = mid + 1
			else:
				hi = mid - 1
	return maximus if maximus > -1 else 0

T = int(input())

def rec_ot(t0, t):
	if t0 < t:
		mid = (t0+t)/2
		rec_ot(t0, mid)
		rec_ot(mid+1, t)
	else:
		N = int(input())
		ar = list(map(int, input().strip("\n").split()))
		br = list(map(int, input().strip("\n").split()))
		print(split_arr(ar, br, N))	

rec_ot(0, T-1)

# for _ in xrange(T):
# 	N = int(raw_input())
# 	ar = map(int, raw_input().strip("\n").split())
# 	br = map(int, raw_input().strip("\n").split())
# 	print split_arr1(ar, br, 0, N-1, N)


tc=int(input())
while tc>0:
	tc-=1
	Pmax = 0;
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	for i in range(n):
		low = 0
		high = n-1
		pos=0
		while low <= high:
			mid = low + (high - low) / 2
			if b[mid] >= a[i]:
				pos = mid
				low = mid + 1
			else:
				high = mid - 1
			
		Pmax=max (Pmax, pos-i)
	print(Pmax)

	
	


tc = int(input())
while tc>0:
	tc = tc - 1
	curMax = 0
	n = int(input())
	x = list(map(int, input().split()))
	y = list(map(int, input().split()))
	for i in range(n):
		low, high, pos = 0, n - 1, -1
		while low<=high:
			mid = (low + high) / 2
			if y[mid] >= x[i]:
				pos = mid
				low = mid + 1
			else:
				high = mid - 1
		curMax = max (curMax, pos - i)
	print(curMax)



import sys
t=int(input())
while t>0:
	t-=1
	n=int(input())
	arr1=list(map(int,input().split()))
	arr2=list(map(int,input().split()))
	ans=0
	l=1

	for i in range(n):
		
		r=n-1
		
		while r>0 and l<r and l<n:
			
			mid=(l+r+1)/2
			#print "Checking %d %d %d"%(l,mid,r)
			if arr2[mid]>=arr1[i]:
				l=mid
				ans=max(ans,mid-i)
			else:
				r=mid-1
			#print l,mid,r
			sys.stdout.flush()
		#print ' '
	print(ans)		


def binsearch(arr,m):
	answer=-1
	low=0
	high=len(arr)-1
	while low<=high:
		mid=(low+high)/2
		if arr[mid]>=m:
			answer=mid
			low=mid+1
		elif arr[mid]<m:
			high=mid-1
	if low>high and answer==-1:
		return 0
	else:
		return answer
	
tc=eval(input())
res=[]
for i in range(tc):
	  res=[]
	  n=eval(input())
	  a=[int(i) for i in input().split()]
	  b=[int(i) for i in input().split()]
	  for i in range(n):
		  num1=a[i]
		  j=binsearch(b,num1)
		  res.append(j-i)
	  res.sort(reverse=True)
	  print(res[0])


for i in range(eval(input())):
	N = eval(input())
	A = list(map(int, input().split()))
	B = list(map(int , input().split()))
	monkiness = 0
	# index of B
	j = N - 1
	while (j - i) > monkiness:
		left = 0
		right = j
		
		if (right - left) <= monkiness:
			break
		
		while left <= right:
			mid = (left + right) / 2
			if A[mid] <= B[j]:
				if monkiness < (j - mid):
					monkiness = j - mid
				right = mid - 1
			else:
				if monkiness >= (j - mid):
					break
				else:
					left = mid + 1
		j -= 1
	
	print(monkiness)


def binsearch(B,Ai,i,N):
	mid=0
	pos=0
	m=N-1
	while i<=m:
		mid=(i+m)/2
		if B[mid]<Ai:
			m=mid-1
		elif B[mid]>=Ai:
			pos=mid
			i=mid+1
	return pos

if __name__ == "__main__":
	for tc in range(int(input())):
		N=int(input())
		A=list(map(int,input().split()))
		B=list(map(int,input().split()))
		ans=0
		for i in range(N):
			j=binsearch(B,A[i],i,N)
			ans=max(ans,j-i)
		print(ans)


def search(a,target,l,h):
	
	mid=(l+h)/2
	if(a[mid]<=target) and (mid==l or (mid>l and a[mid-1]>target)):
		return mid
	if (a[mid]>target and (mid<h-1 and a[mid+1]<=target)):
		return mid+1
	if (a[mid]>target):
		return search(a,target,mid+1,h)
	if (a[mid]<=target):
		return search(a,target,l,mid-1)
		
t=eval(input())
while(t>0):
	n=eval(input())
	A=[int(x) for x in input().split()]
	B=[int(x) for x in input().split()]
	max=0
	j=0
	i=0
	while(j<n):
		if(B[j]>=A[j]):
			i=search(A,B[j],0,j)
			#print B[j],i
			if((j-i)>max):
				max=j-i
			
		j=j+1
	print(max)
	t=t-1


tc=int(input())
while tc>0:
	tc-=1
	Pmax = 0;
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	for i in range(n):
		low = 0
		high = n-1
		pos=0
		while low <= high:
			mid = (low + high) / 2
			if b[mid] >= a[i]:
				pos = mid
				low = mid + 1
			else:
				high = mid - 1
			
		Pmax=max (Pmax, pos-i)
	print(Pmax)