BRDGHRD  Building Bridges(HARD)
The tribe soon discovers that just communication is not enough and wants to meet each other to form a joint force against the terminator.But there is a deep canyon that needs to crossed. Points have been identified on both sides on which bridge ends can be made. But before the construction could be started, a witch Chudael predicted that a bridge can only be built between corresponding end points, i.e. a bridge starting from the i^{th} end point on one side can only end on the i^{th} end point on the other side, where the position of end points is seen in the order in which the points were identified. If not, it would lead to the end of the tribe. The tribe just wants to make as many nonoverlapping bridges as possible, with the constraint in mind.
Input
The first line of the input contains test cases t. It is followed by 3*t lines, 3 for each test case. The first line of input for each test case contains the number of end points identified on each side, n (1<=n<=10^{5}). The second line contains xcoordinates of end points identified on the first side and similiarly the third line contains the xcoordinates of corresponding end points identified on the other side. The end points are inputted in the order in which they were identified. The xcoordinates can range between 10^{6} to 10^{6}.
Output
You are required to output a single line for each test case. The line contains a single integer – the
maximum number of bridges possible with the constraints explained above.
Example
Input:
34
2 5 8 10
6 4 1 2
3
5 3 10
6 4 1
6
1 2 3 4 5 6
3 4 5 6 1 2
Output:2
2
4
Expalanation: For the first test case, two nonoverlapping bridges can be formed between the 3rd
and 4th end points on each side.
(This problem is based on: http://www.spoj.com/problems/BRIDGE.)
hide comments
aroder:
20190130 09:12:40
Seg tree giving wrong answer


Sigma Kappa:
20170703 11:50:47
Is it true that the first list of the xcoordinates is already sorted?


karthik1997:
20160603 11:34:22
http://www.geeksforgeeks.org/longestmonotonicallyincreasingsubsequencesizenlogn/ and you need to do some changes. to get AC as that is only for strictly increasing subsequence :p Last edit: 20160603 11:39:43 

anando_du:
20150304 17:19:06
easy problem ! but O(n^2) won't work ! O(nlogk) will work fine :) 

Hussain:
20140508 21:48:15
You call this hard?


bat2009fifa:
20131126 21:08:18
1

Added by:  Aleksandar Abas 
Date:  20130427 
Time limit:  0.140s0.25s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  Based on: Building Bridges By Troika::Bytes 