Maximum Distance

Interview

Time limit1sMemory limit128 MB

Summary

Given two non-increasing arrays, find the largest j - i such that j >= i and Y[j] >= X[i].

Level: Medium4 of 10
Topics: Array, Two pointers, Greedy, Sorting
Solved: No attempts yet

Problem

Consider two non-increasing integer sequences $X[0..n-1]$ and $Y[0..n-1]$ , where $X[i] \ge X[i+1]$ and $Y[i] \ge Y[i+1]$ for all $0 \le i < n-1$ .

The distance $d(X[i], Y[j])$ between two elements $X[i]$ and $Y[j]$ is $j - i$ if $j \ge i$ and $Y[j] \ge X[i]$ , and $0$ otherwise.

The distance between the sequences $X$ and $Y$ is

$d(X, Y) = \max\{\, d(X[i], Y[j]) \mid 0 \le i < n,\ 0 \le j < n \,\}.$

For example, for the sequences $X$ and $Y$ shown below, the maximum is attained at $i = 2$ and $j = 7$ , so $d(X, Y) = d(X[2], Y[7]) = 5$ .

Input

The first line contains the number of test cases $T$ . Each test case consists of three lines: the first line contains the sequence length $n$ ( $0 < n < 1000$ ); the second line contains the $n$ elements of sequence $X$ separated by spaces; the third line contains the $n$ elements of sequence $Y$ separated by spaces. Both sequences are non-increasing and have equal length.

Output

For each test case, print a single line The maximum distance is d, where $d$ is the value of $d(X, Y)$ . Separate the output of consecutive test cases with one blank line.

Examples2

Example 1

Input

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

Expected output

The maximum distance is 5

The maximum distance is 0

Example 2
Input
```
1
1
5
5
```
Expected output
```
The maximum distance is 0
```