题目描述

给定一个由 $N$ 个正整数组成的序列 $A=(A_1,A_2,\ldots,A_N)$。

对于每个 $k$（$1\le k\le N$），求解以下问题：

令 $B$ 最初为序列 $(A_1,A_2,\ldots,A_k)$。在操作过程中的任意时刻，用 $|B|$ 表示 $B$ 当前的长度，用 $B_i$ 表示它的第 $i$ 个元素。

你可以执行任意次以下操作。

• 选择一个下标 $i$（$1\le i\le |B|$），满足 $i+B_i-1\le |B|$。从 $B$ 中删除元素 $B_i,B_{i+1},\ldots,B_{i+B_i-1}$。剩余元素按照原来的相对顺序组成新的序列 $B$。

判断是否可以将 $B$ 变为空序列。如果可以，求所需操作次数的最小值和最大值。

输入格式

输入包含一组测试数据，格式如下。

N
A_1 A_2 ... A_N

第一行包含一个整数 $N$（$1\le N\le5000$），表示序列的长度。

第二行包含 $N$ 个整数 $A_1,A_2,\ldots,A_N$（$1\le A_i\le N$）。

输出格式

输出 $N$ 行。

对于每个 $k$（$1\le k\le N$），第 $k$ 行输出 $B=(A_1,A_2,\ldots,A_k)$ 对应的答案。如果无法将 $B$ 变为空序列，输出 -1。否则，输出两个整数，分别表示将 $B$ 变为空序列所需操作次数的最小值和最大值。

5
3 4 2 1 1

-1
-1
1 1
2 2
2 3

6
2 1 3 2 1 2

-1
1 1
2 2
-1
2 3
3 4