Algorithms, Breadth First Search, Breadth-first search, Easy-Medium, Graph

Problem

Editorial

Analytics

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

Marking Scheme: Marks are awarded when all the testcases pass.

Allowed Languages: Bash, C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, TypeScript, Visual Basic

CODE EDITOR

Initializing Code Editor...

View all comments

Contributor

This Problem was Asked in

Challenge Name

June Easy' 19

All Tracks Algorithms Graphs Breadth First Search Problem

Algorithms, Breadth First Search, Breadth-first search, Easy-Medium, Graph

CODE EDITOR

Contributor

This Problem was Asked in

Social Share