题目背景

ほら行くよって$\\$ 手を引いてくれた君は$\\$ 綺麗な目して言うんだ$\\$ 僕らあの頃と$\\$ 何も変わらないから$\\$ せめて$\\$ 二人で夢を見させて

—— さよならワンダーランド - Nanatsukaze

能够带你进入孩童时期的梦境中的那个人，该在哪里寻找呢？

题目描述

给定序列 $a_1, a_2, \dots, a_n$，请对于每一个 $1\sim n$ 的整数 $i$ 求任意一个整数 $j$ 使得以下条件同时成立，或判断不存在这样的 $j$：

• $1\leq i+j\leq n$；
• $a_i \leq j \leq a_{i+j}$。

输入格式

第一行一个整数 $n$。

接下来一行 $n$ 个空格分隔的整数 $a_1,a_2,\dots,a_n$。

输出格式

输出 $n$ 行。

对于第 $i$ 行，如果能够找到 $j$ 使得 $1\leq i+j\leq n$ 且 $a_i \leq j \leq a_{i+j}$ 成立，则先输出一个 $1$，再输出你找到的 $j$，空格分隔。如果有多个合法 $j$ 可输出任意一个。如果不存在这样的 $j$，则仅输出一个 $0$。

3
-1 1 4

1 2
1 1
0

5
1 -1 0 2 -3

0
1 -1
1 0
0
1 -3

提示

【样例解释 #1】

$i=1,j=2$ 时，$a_i=-1$，$a_{i+j}=4$，满足 $a_i\leq j\leq a_{i+j}$。

$i=2,j=1$ 时，$a_i=1$，$a_{i+j}=4$，满足 $a_i\leq j\leq a_{i+j}$。

$i=3$ 时可以证明不存在符合条件的 $j$。

【数据范围】

对于所有数据，保证 $1\leq n \leq 3\times 10^5$，$-10^9\leq a_i\leq 10^9$。

捆绑测试，共 3 个 Subtask，具体限制如下所示：

• Subtask 1（17 pts）：$n\leq 1000$。
• Subtask 2（39 pts）：对所有 $1\leq i\leq n$ 保证 $a_i\leq -i$。
• Subtask 3（44 pts）：无特殊限制。