Problem Description

Given a circle with \( n \) points on it, the distance between each pair of adjacent points is \( 1 \).

Each point has two attributes \( a_i \) and \( b_i \). For point \( i \), define \( f_i \) as the shorter distance on the circle between point \( i \) and the nearest point \( j \) such that \( a_j \ge b_i \), where \( i \ne j \). If no such \( j \) exists, \( f_i = -1 \).

Input Format

The input consists of 3 lines.
- The first line contains one integer \( n \).
- The second line contains \( n \) integers, where the \( i \)-th integer represents \( a_i \).
- The third line contains \( n \) integers, where the \( i \)-th integer represents \( b_i \).

Output Format

Output one line containing \( n \) integers, where the \( i \)-th integer represents \( f_i \).

Sample Input and Output

Sample Input #1

3
1 2 3
3 2 1

Sample Output #1

1 1 1

Sample Input #2

5
5 4 3 5 6
7 6 5 4 3

Sample Output #2

-1 2 1 1 1

Sample Input #3

5
1 1 2 1 1
2 2 2 2 2

Sample Output #3

2 1 -1 1 2

Notes

For \( 20\% \) of the data, \( 1 \le n \le 10^3 \).
For \( 100\% \) of the data, \( 1 \le n \le 10^5 \), \( 1 \le a_i, b_i \le 10^9 \).

We use bundled testing for test cases 4 to 11.

Sample 1 Explanation

For \( i = 1 \), \( a_3 = 3 = b_1 = 3 \), the distance between \( 1 \) and \( 3 \) is \( 1 \), so \( f_1 = 1 \).
For \( i = 2 \), \( a_3 = 3 > b_2 = 2 \), the distance between \( 2 \) and \( 3 \) is \( 1 \), so \( f_2 = 1 \).
For \( i = 3 \), \( a_2 = 2 > b_3 = 1 \), the distance between \( 2 \) and \( 3 \) is \( 1 \), so \( f_3 = 1 \).

Updated on March 30, 2021: Added a hack data set, which disqualified a submission by user wu0615.

见题面 Input 部分

见题面 Output 部分