Problem Description

You are given a sequence of $N$ positive integers $A=(A_1,A_2,\ldots,A_N)$.

For each $k$ ($1\le k\le N$), solve the following problem:

Let $B$ initially be the sequence $(A_1,A_2,\ldots,A_k)$. At any point during the process, let $|B|$ denote the current length of $B$ and let $B_i$ denote its $i$-th element.

You may perform the following operation any number of times.

• Choose an index $i$ ($1\le i\le |B|$) satisfying $i+B_i-1\le |B|$. Remove the elements $B_i,B_{i+1},\ldots,B_{i+B_i-1}$ from $B$. The remaining elements, in their original order, form the new sequence $B$.

Determine whether $B$ can be made empty. If so, find the minimum and maximum possible numbers of operations required.

Input Format

The input consists of a single test case of the following format.

N
A_1 A_2 ... A_N

The first line contains an integer $N$ ($1\le N\le5000$), representing the length of the sequence.

The second line contains $N$ integers $A_1,A_2,\ldots,A_N$ ($1\le A_i\le N$).

Output Format

Print $N$ lines.

For each $k$ ($1\le k\le N$), the $k$-th line should contain the answer for $B=(A_1,A_2,\ldots,A_k)$. If it is impossible to make $B$ empty, print -1. Otherwise, print two integers: the minimum and maximum possible numbers of operations required to make $B$ empty, respectively.

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