Algorithms, Breadth First Search, Graphs

Problem

Editorial

Analytics

Discussions NEW

You are standing at position $1$. From position $$i$$, you can walk to $$i+1$$ or $$i-1$$ with cost $1$. From position $i$, you can travel to without any cost to $$p_i$$ ($p$ is a permutation of numbers $1 \ldots n$). You have to reach position $n$. Determine the minimum possible cost.

Input format

First line: $T$ denotes the number of test cases ($1 \le T \le 10$)
For each test case:
- First line: $n$ ($1 \le n \le 50\ 000$)
- Second line: $n$ integers where the $i_{th}$ integer is $p_i$
  Note: It is guaranteed that $p$ is a permutation.

Output format
Print the minimum possible cost.

SAMPLE INPUT

6
6
1 4 3 2 5 6
6
3 2 6 5 4 1
6
3 6 2 4 1 5
6
5 4 6 3 2 1
6
1 6 5 4 2 3
6
5 1 3 6 2 4

SAMPLE OUTPUT

Explanation

Time Limit: 2.0 sec(s) for each input file.

Memory Limit: 256 MB

Source Limit: 1024 KB

Algorithms, Breadth First Search, Graphs

Best Submission

Similar Problems

Contributors

This Problem was Asked in