Background

Original problem link: https://oier.team/problems/X6D。

Look, let’s go$\\$ You held my hand and pulled me along$\\$ With those beautiful eyes, you said$\\$ We are just like back then$\\$ Nothing has changed$\\$ At least$\\$ Let the two of us dream together

—— Sayonara Wonderland - Nanatsukaze

Where should we look for the person who can lead you into the dreams of your childhood?

Problem Description

Given a sequence $a_1, a_2, \dots, a_n$, for each integer $i$ from $1$ to $n$, find any integer $j$ such that all of 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}$。

Input Format

The first line contains an integer $n$。

The next line contains $n$ space-separated integers $a_1, a_2, \dots, a_n$。

Output Format

Output $n$ lines。

For the $i$-th line, if you can find a $j$ such that $1 \leq i + j \leq n$ and $a_i \leq j \leq a_{i+j}$ both hold, first output $1$, then output the $j$ you found, separated by a space. If there are multiple valid $j$, you may output any one of them. If no such $j$ exists, output only $0$。

3
-1 1 4

1 2
1 1
0

5
1 -1 0 2 -3

0
1 -1
1 0
0
1 -3

Hint

Sample Explanation #1

When $i = 1, j = 2$, we have $a_i = -1$ and $a_{i+j} = 4$, satisfying $a_i \leq j \leq a_{i+j}$。

When $i = 2, j = 1$, we have $a_i = 1$ and $a_{i+j} = 4$, satisfying $a_i \leq j \leq a_{i+j}$。

When $i = 3$, it can be proven that no $j$ satisfies the conditions。

Constraints

For all testdata, it is guaranteed that $1 \leq n \leq 3 \times 10^5$ and $-10^9 \leq a_i \leq 10^9$。

Bundled tests, with a total of 3 subtasks. The specific limits are as follows:

• Subtask 1 (17 pts): $n \leq 1000$。
• Subtask 2 (39 pts): For all $1 \leq i \leq n$, it is guaranteed that $a_i \leq -i$。
• Subtask 3 (44 pts): No additional constraints。

Translated by ChatGPT 5