Mountain Horizon

You travel through a scenic landscape consisting mostly of mountains – there are \(n\) landmarks (peaks and valleys) on your path. As you catch your breath, you wonder: which mountain are you currently seeing on the horizon?

Formally: You are given a polygonal chain of points \(P_1, P_2, \cdots, P_n\) in the plane. The \(x\)-coordinates of the points are in strictly increasing order. For each segment \(P_iP_{i+1}\) (for \(1 \le i \le n-1\)) of this chain, find the smallest index \(j\) (with \(j>i\)) for which any point of segment \(P_jP_{j+1}\) is visible from segment \(P_iP_{i+1}\). A point \(Q\) on segment \(P_jP_{j+1}\) is said to be visible if it lies strictly above the ray starting at \(P_i\) and passing through \(P_{i+1}\). In other words, if we denote \(\vec{v}=P_{i+1}-P_i\), and for any point \(Q\) consider the cross product \(\vec{v}\times (Q-P_i)\), then \(Q\) is visible if \(\vec{v}\times (Q-P_i) > 0\>.

inputFormat

The first line contains an integer \(n\) (\(n \ge 2\)), representing the number of landmarks.

Each of the next \(n\) lines contains two integers \(x\) and \(y\) (coordinates of a landmark). The \(x\)-coordinates are given in strictly increasing order.

outputFormat

Output \(n-1\) integers. The \(i\)-th integer (for \(1 \le i \le n-1\)) is the smallest index \(j\) (with \(j > i\)) such that the segment \(P_jP_{j+1}\) is visible from the segment \(P_iP_{i+1}\), according to the definition above. If there is no such segment, output \(-1\) for that \(i\). The indices are 1-indexed.

sample

4
0 0
1 1
2 0
3 2

-1 3 -1