P11157 [MX-X6-T3] Sayonara Wonderland

Original problem link: 。 --- > _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](https://music.163.com/#/song?id=2053736409)_ Where should we look for the person who can lead you into the dreams of your childhood?

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}$。

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

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$。

**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