Mountainous landscape#7718
You travel through a scenic landscape consisting mostly of mountains — there are landmarks (peaks and valleys) on your path. You pause for breath and wonder: which mountain are you currently seeing on the horizon?
Formally: you are given a polygonal chain P_1P_2\ldots P_n in the plane. The coordinates of the points are in strictly increasing order. For each segment P_iP_{i+1} of this chain, find the smallest index j > i, for which some point of P_jP_{j+1} is visible from P_iP_{i+1} (lies strictly above the ray P_iP_{i+1}).
The first line contains the number of test cases . The descriptions of the test cases follow.
The first line of each test case contains an integer (2 \leq n \leq 10^5) — the number of vertices on the chain. Each of the following lines contains integer coordinates x_i, y_i of the vertex P_i (0 \leq x_1 < x_2 < \ldots < x_n \leq 10^9,\ 0 \leq y_i \leq 10^9).
For each test case, output a single line containing n - 1 space-separated integers. These should be the smallest indices of chain segments visible to the right, or when no such segment exists.
Example 1