Minimum cost
Tag(s):

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
3
0
0
0
1
1

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...

## This Problem was Asked in

Challenge Name

June Easy' 19

OTHER PROBLEMS OF THIS CHALLENGE
• Basic Programming > Input/Output
• Algorithms > Sorting
• Algorithms > Greedy Algorithms
• Math > Basic Geometry
• Algorithms > Graphs