Do you think yesterday's problem was hard?
Don't be sad here is an easy problem to encourage you to continue or Ali will be mad at you :)
Given an array $a$ for each $i$, find min $j$ such that $(i - j) <= (a_i + a_j$) or print $-1$ if there is no such $j$
The input consists of multiple test cases. The first line contains a single integer $t (1 \le t \le 10^4)$ --- the number of test cases.
The first line of each test case contains one integer $n (1 \le n \le 2 \cdot 10^5)$ --- the number of elements in the array $a$.
The second line of each test case contains $n$ integers $a_1,a_2, \dots ,a_n (-10^9 \le a_i \le 10^9)$ the elements of the array $a$.
It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.
For each test case, print $n$ integers as described in the problem statement.
Input | Output |
---|---|
2 5 -1 8 -5 7 -1 6 1 2 -3 4 -5 6 Copy
|
2 1 2 1 2 1 1 4 1 6 1 Copy
|
First reorder the equation to be i - a[i] <= j + a[j] instead of i - j <= a[i]+ a[j].
Then store all the values of i - a[i], call it $v$ then sort it.
Now we want for each j from 1 to n to find the first (j + a[j]) that is greater than or equal to $v$
We can make pre-calculate the minimum index j: iterate starting from the end of the vector and store for each value in $v$ the minimum $j$ so far.