이동하기

수직선 위의 $1$번 위치에서 $N$번 위치까지 이동하려고 한다. $i$번 위치에서는 $1,2,\cdots,A_i$ 가운데 하나만큼 오른쪽으로 이동할 수 있다.

$N$번 위치에 정확히 도달하기 위한 최소 이동 횟수를 구하여라. 도달할 수 없다면 -1을 출력하여라.

입력은 다음과 같은 형식으로 주어진다.

$T$ case$_1$ case$_2$ $\vdots$ case$_T$

각 테스트 케이스는 다음과 같은 형식으로 주어진다.

$N$ $A_1\ A_2\ \cdots\ A_N$

각 테스트 케이스마다 최소 이동 횟수를 한 줄에 출력한다. 도달할 수 없다면 -1을 출력한다.

• $1 \leq T \leq 100$.
• $1 \leq N \leq 200\,000$.
• $0 \leq A_i \leq N$ ($1 \leq i \leq N$).
• 모든 테스트 케이스에 대한 $N$의 합은 $200\,000$ 이하이다.