Description

A cycle is given with $n$ points on it, where the distance between every pair of adjacent points is $1$.

Each point has two attributes $a_i$ and $b_i$. For point $i$, define $f_i$ as the shortest distance along the cycle between $i$ and a point $j$ such that $i \ne j$ and $a_j \ge b_i$. In particular, if there is no such $j$, then $f_i=-1$.

Input Format

The input has $3$ lines.
Line $1$ contains one integer $n$.
Line $2$ contains $n$ integers, where the $i$-th integer denotes $a_i$, with the same meaning as above.
Line $3$ contains $n$ integers, where the $i$-th integer denotes $b_i$, with the same meaning as above.

Output Format

Output one line with $n$ integers, where the $i$-th integer denotes $f_i$, with the same meaning as above.

3
1 2 3
3 2 1

1 1 1

5
5 4 3 5 6
7 6 5 4 3

-1 2 1 1 1

5
1 1 2 1 1
2 2 2 2 2

2 1 -1 1 2

Hint

Constraints

For $20\%$ of the testdata, $1 \le n \le 10^3$.
For $100\%$ of the testdata, $1 \le n \le 10^5$, $1 \le a_i,b_i \le 10^9$.

For test points $4$ to $11$, we use bundled evaluation.

Explanation of Sample 1

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$.

$\text{Upd 2021.3.30}$: Added a set of hack testdata.

Translated by ChatGPT 5