Assume, in a forest there are n trees and ith tree is at position i, for i =1 …n. These trees are having different heights. Let us assume that the tree i is having nonnegative heights hi feet. One day the forester has decided to trim the heights or uproot the trees to arrange the rooted trees with respect to their heights. That is, at the end of the operation, rooted trees satisfy the property of hi < hj for i < j. Note that if one uproots a tree, then it cannot be placed back in any place and hence it is no longer in the forest.
The problem is to determine is the minimum cutting of wood required to make sure that all remaining trees satisfy the height property.
The input may contain multiple test cases.
Each test case contains a sequence of n integers to indicate the heights of n trees in the forest. The ith integer indicates the height of the ith tree.
For each test case, output is the total length of the wood cut. It is followed by a line which tells the amount of cut from each tree, i.e., ith element in the line tells the amount of cut in the ith tree. Next line contains the information about the final height of each tree which means that ith element in that line tells the current height of the ith tree. If a tree is uprooted, then mark its final height as ‘x’.
2 5 1 2 7
0 0 1 2 0
2 5 x x 7