Finding a Valid Shift

Given a sequence \(a_1, a_2, \dots, a_n\), for each integer \(i\) from \(1\) to \(n\) find any integer \(j\) such that the following conditions hold, or determine that no such \(j\) exists:

• \(1 \leq i+j \leq n\).
• \(a_i \leq j \leq a_{i+j}\).

If there is no valid \(j\) for a given \(i\), output \(-1\) for that \(i\). The answer for all \(i\) should be printed in order, separated by spaces.

inputFormat

The first line contains an integer \(n\) representing the number of elements in the sequence.

The second line contains \(n\) integers \(a_1, a_2, \dots, a_n\) separated by spaces.

outputFormat

Output a single line containing \(n\) integers. For the \(i\)-th position, output any valid \(j\) satisfying the conditions, or \(-1\) if no such \(j\) exists.

sample

5
1 -1 2 2 3

2 -1 2 -1 -1