Chef y el salto de dígitos

Points: 100 (partial)

Time limit: 1.0s

Memory limit: 64M

Author:

Problem type

Allowed languages

Ada, Assembly, Awk, BrainF***, C, C#, C++, Dart, Go, Java, JS, Kotlin, Lua, Pascal, Perl, Prolog, Python, Scala, Swift, VB

A Chef le gustan los juegos. Pero el quiere inventar su propio juego. Chef tiene una sequencia de dígitos $S_1, S_2, \ldots , S_N$ ~S_1, S_2, \ldots , S_N~,. Él se encuentra ubicado en el primer dígito ( $S_1$ ~S_1~) y quiere alcanzar el último dígito ( $S_N$ ~S_N~) en el mínimo número de saltos. Mientras esté ubicado en algún dígito $x$ ~x~ con índice $i$ ~i~ (dígito $S_i$ ~S_i~) Chef puede saltar hacia los dígitos con índices $i - 1$ ~i - 1~ ( $S_{i-1}$ ~S_{i-1}~) e $i + 1$ ~i + 1~ ( $S_{i+1}$ ~S_{i+1}~) pero no puede saltar fuera de esa secuencia. O también puede saltar hacia cualquier dígito con el mismo valor $x$ ~x~. Ayuda a Chef a encontrar el mínimo número de saltos que necesita para alcanzar el dígito $S_N$ ~S_N~ empezando en el dígito $S_1$ ~S_1~.