Circular Distance Query

Given a circle with n vertices where the distance between every pair of adjacent vertices is 1, each vertex i is assigned two attributes: \(a_i\) and \(b_i\). For each vertex i, define

\(f_i = \min\{ d(i,j) : j \neq i \text{ and } a_j \geq b_i \}\)

where the distance \(d(i,j)\) on the circle is given by \[ d(i,j) = \min(|i-j|,\, n-|i-j|)\] If no vertex j satisfies \(a_j \geq b_i\), then \(f_i = -1\).

inputFormat

The first line contains an integer (n). Each of the following (n) lines contains two integers (a_i) and (b_i), representing the attributes of vertex i.

outputFormat

Output a single line containing (n) integers, where the i-th integer is (f_i). Separate the numbers by a single space.

sample

3
3 1
2 3
4 2

1 1 1