Given an array of integers \(A\) of size \(N\).
You can perform the following operation on the array:
- Choose an index \(i\) and remove the \(i^{th}\) element from \(A\).
For each, \(i\) (from \(1\) to \(N\)), output the minimum number of operations such that the integer \(i\) becomes greater than BOTH of its neighbours i.e. \((A[i] > A[i-1] \ \ \&\& \ \ A[i] > A[i+1])\).
If it is not possible to satisfy the mentioned condition output \(-1\) for that index
Input Format :
The first line contains \(T\), the number of test cases
The first line of all test cases contains \(N\), the number of elements in the array
The second line contains \(N\) space-separated integers
Note : The sum of \(N\) over all test cases does not exceed \(10^5\)
Output Format :
For every test case, output \(N\) integers, where the \(i^{th}\) integer represents the minimum number of moves to make the \(i^{th}\) index good
Constraints:
\(1 \leq T \leq 100 \\ 1 \leq N \leq 10^5 \\ 1 \leq A[i] \leq 10^9 \\\)
For the given sample, T = 1, N = 5
A = [1, 2, 3, 5, 1]
For i = 1
Since there is no left neighbor, output -1
For i = 2
We can perform two operations and remove 3 and 5.
A becomes [1, 2, 1]
Hence, 2 is greater than both of its neighbors
So, answer is 2.
For i = 3
Remove 5, A = [1, 2, 3, 1].
So, answer is 1
For i = 4
5 is already greater than both of its neighbors.
So, answer is 0
For i = 5
Since there is no right neighbor, answer is -1
