How to find minimum pairing cost? (Any Language)

I came across an algorithm question recently and I still haven't been able to come up with a way to solve it. Can anyone help with pseudocode or logic?

Here is the question: There are n elements in the array. N is an odd number. When we exclude 1 element from array, we are finding the minimum pairing cost.

Rules:

1 <= n <= 1001

n % 2 = 1

Example:

Given array is [4, 2, 1, 7, 8]

When we pair items with the closest ones [[1,2], [7,8]] and "4" is excluded. So the minimum cost is |1 - 2| + |7 - 8| = 2;

What i tried:

Sort array first: [1,2,4,7,8]
Remove the middle element: 4
Pair items with the next ones: [[1, 2], [7, 8]]

According the example it works but what if the given array is [1, 7, 8, 16, 17]?

Sort array first: [1, 7, 8, 16, 17]
Remove the middle element: 8
Pair items with the next ones: [[1, 7], [16, 17]] Wrong Answer
"1" must be excluded and the pairs must be [[7, 8], [16, 17]]

Solution

Once the array is sorted, you can pair all elements from left to right, keep track of the total sum, and replace the last pairing with one starting from the right, updating the total sum if it's smaller.

In pseudo-code (all zero-based indexing):

let S be the sum of all pairing costs of
elements 2i and 2i+1 for i from 0 to (n-3)/2
(that is all pairings when you exclude the very last element)

let j = (n-1)/2
for i from (n-3)/2 to 0 (included):
    let L be the pairing cost of elements 2i and 2i+1
    let R be the pairing cost of elements 2i+1 and 2i+2
    let S' = S - L + R
    if S' < S
        replace S with S'
        replace j with i

2j is the element to exclude