DP Problem Doubt Atcoder Educational DP Contest

#1

Problem - https://atcoder.jp/contests/dp/tasks/dp_a

My solution - https://atcoder.jp/contests/dp/submissions/6893436

Doubt - What would be the smart approach to modify my solution if they also wanted to print the path that i chose as well as the minimum cost?

Example -
I/P ->
6
30 10 60 10 60 50
O/P->
If we follow the path 11 → 33 → 55 → 66, the total cost incurred would be |30−60|+|60−60|+|60−50|=40|30−60|+|60−60|+|60−50|=40.

#2

Make an array initialize arr[i]=i.Then for each elements update who is its parent .Then from nth element go back until parent of the element is the same element.