Minimum Moves - JMPC IIT Roorkee

Problem Preview

"### Problem Given an array A of length N that contains the numbers from 1 to N in any order. It is allowed to move from an index i to an index i+1 or index A[i] in one move. You are required to reach to Index N+1 from all Index i with minimum moves and take the sum of these minimum moves. Find and print the required sum. ### Note * You have to consider the minimum number of moves to reach from an index i to an index N+1. * All the paths to index N+1 go via index N. * Consider 1 based indexing. ### Input Format The input consists of two lines: * The first line contains an integer N. * Next line contains N integers A[i] which is the permutation of length N. The input will be read from the STDIN by the candidate. ### Output Format * Print a number that represents the sum of the minimum moves from all the indexes to reach index N+1. * The output will be matched to the candidate's output printed on the STDOUT. ### Example 1: Input: 7 3 2 1 7 4 6 5 Output: 4 ### Explanation: N=7. A:13217465 * To go from an index i to an index N + 1 - i requires 4 moves. * Similarly, index 2 to index 8: 4 moves * index 3 to index 8: 3 moves * index 4 to index 8: 2 moves * index 5 to index 8: 3 moves * index 6 to index 8: 2 moves * index 7 to index 8: 1 move * total moves=19"