P17575 [JAG 2026 Summer Camp #3] Self-Destruct Sequence

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.

The input consists of a single test case of the following format. ```text 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$).

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.