Minimize Sum of Adjacent Differences

You are given a sequence of integers. Your task is to compute the minimum cost required to modify the sequence so that the sum of the absolute differences between adjacent elements is minimized.

Observation: When the sequence is sorted in non-decreasing order, the sum of differences between adjacent elements is:

\(\sum_{i=1}^{n-1} (a_{i+1} - a_i) = a_n - a_1\)

This is the minimum possible sum. For example, consider the sequence [3, 1, 4, 1, 5]. After sorting, it becomes [1, 1, 3, 4, 5] and the cost is \(5-1=4\).

Your program should read an integer n representing the number of elements, followed by n integers, and then output the minimal cost.

inputFormat

The first line of the input contains a single integer n, the number of elements in the sequence.

The second line contains n space-separated integers representing the sequence.

outputFormat

Output a single integer – the minimum cost to modify the sequence so that the sum of adjacent differences is minimized.

5
3 1 4 1 5

4