Given a sequence input as a circular array, which means that the element next to the last number in the array is the first number. For each number in the input, you need to find the relative position of its preceding closest larger element (PCLE).
Given the i-th element in the circular array A, denoted as A[ i ], the PCLE of A[ i ] satisfies both the following requirements. Let the PCLE of A[ i ] be the j-th element in A, i.e., A[ j ]:
i) A[ i ] < A[ j ]
ii) if j < i, then ( i - j ) is minimum, for all j;
Otherwise, ( i + n - j ) is minimum, for all j , where n is the number of elements in array A
We define the relative position as the index of an element's PCLE minus its own index. That is, you need to output the value of ( j - i ).
For instance, assume array A = [8,6,9,3,7,11,2,12,5,4]. The PCLE of value 8 is 12. Since A is a circular array, the searching sequence would be 8 -> 4 -> 5 ->12. Since the indices of values 8 and 12 are 0 and 7, respectively, the relative position between 8 and 12 is 7. We output 7.
Another example is that the PCLE of 7 is 9, and the searching sequence would be 7 -> 3 -> 9. The relative position between 7 and 9 is -2, and thus we output -2.
If there is no PCLE of the given element, then output 0.
Note that all STL library are forbidden.
The input includes the elements in the array A, as a line of integers separated by spaces. That is, the first integer is the first element in A, the second integer is the second element in A, and so on.
1 <= value of each integer <= 100000
1 <= total number of integers <= 200000
Assume there are n elements in A, your program needs to output n integers, which are the relative positions of the PCLE of A[0] to A[n-1].
Please note that there is a space following each integer, including the last output integer.
Please output a newline at the end.