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 ith end point on one side can only end on the ith 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 non-overlapping 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 <= 105). The second line contains x-coordinates of end points identified on the first side and similarly the third line contains the x-coordinates of corresponding end points identified on the other side. The end points are inputted in the order in which they were identified. The x-coordinates can range between -106 to 106.

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:
3
4
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

Explanation

For the first test case, two non-overlapping bridges can be formed between the 3rd and 4th end points on each side.

(This problem is based on BRIDGE.)


hide comments
zerojude: 2021-07-25 11:18:17

***be aware of whether strictly increasing ( LIS ) or longest nondecreasing subsequence**
this was the reason for my one wrong submission

aroder: 2019-01-30 09:12:40

Seg tree giving wrong answer

Sigma Kappa: 2017-07-03 11:50:47

Is it true that the first list of the x-coordinates is already sorted?

EDIT: assuming the first list is already sorted, I sort the second list first by x and, in case of ties, by ID, I then find a LIS in the sequence of ID's of the second list... I get WA, what can go wrong?...

EDIT: nevermind, got Accepted, I've overlooked the second sample I/O.

Last edit: 2017-07-03 12:12:52
karthik1997: 2016-06-03 11:34:22

http://www.geeksforgeeks.org/longest-monotonically-increasing-subsequence-size-n-log-n/ and you need to do some changes. to get AC as that is only for strictly increasing subsequence :p

Last edit: 2016-06-03 11:39:43
anando_du: 2015-03-04 17:19:06

easy problem ! but O(n^2) won't work ! O(nlogk) will work fine :)

Hussain: 2014-05-08 21:48:15

You call this hard?
it's hard compared to the previous one

Last edit: 2014-05-24 03:32:12
bat2009fifa: 2013-11-26 21:08:18

1
2
1 4
2 2
ans is 2
yep

Last edit: 2014-01-26 01:22:23

Added by:Aleksandar Abas
Date:2013-04-27
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Based on: Building Bridges By Troika::Bytes