Hard Divide and Conquer > Dynamic Programming

You are given an array of **n** integers. Currently you are at **m**'th (*1 <= m <= n*) position. It is guaranteed that the value of the *m*'th position is the smallest among the all values in the array. You must visit each **position exactly once**. Each time **you must jump** to the position whose value is equal to the current value. If there is no such position then you have to jump the position whose value is minimum among the non-visited values.In order to jump from position *i* to position *j* you have to add ***|i-j|*** steps with your total steps, which is the absolute difference between index i and j. Initially total steps is 0.You have to visit the full array in such a way that total steps become as small as possible. For example, if there are 5 integers: 2 4 3 1 2 and you are at 4th position (1-indexing) then you can visit the full array it in two ways. Way 1: Position 4 -- position 1 – position 5 – position 3 – position 2. (Total number of steps: 3 + 4 + 2 + 1 = 10) Way 2: Position 4 -- position 5 – position 1 – position 3 – position 2. (Total number of steps: 1 + 4 + 2 + 1 = 8) From the above two cases, we can say that **Way 2** is better than **Way 1** as **Way 2** takes less steps to traverse the full array then **Way 1**. Input: ------ Input starts with an integer *T (**1≤ T≤ 5**)*, denoting the number of test cases. Each case contains two lines. The first line of each test case contains two integers which denote the values of **n** and **m**. The second line of each test case contains **n** space separated integers which denote the values of the array. Output: ------- For each case output should contain the minimum number of steps need to traverse the full array. Constraints: ------- **1 <= T <= 10** **1 <= n, m <= 100000 (m <= n)** **1 <= Values in position i <= 100000 (1 <= i <= n)** Sample Input ------------ 2 5 5 2 3 3 2 1 4 3 1 1 1 2 Sample Output ------------- 6 5

Faruk Hossain Milon