Building a Tournament

Each year in World City, (n) players join a World Craft tournament in a fixed draw order. The game is completely decided by skill: whenever two players meet, the player with the smaller ranking number always wins.

You must build a tournament without changing the left-to-right order of the drawn players. You may insert any number of byes, but matches may not cross. Equivalently, every match combines the winners of two adjacent intervals of the draw.

The cost of a match is the absolute difference between the rankings of the two players in that match. The total cost of the tournament is the sum of all match costs. For example, when the draw order is ranks 1, 6, 2, 5, 3, 4, one possible bracket has matches (1, 6), (2, 5), (3, 4), (1, 2), and (1, 3), for total cost (5+3+1+1+2=12). Other valid brackets can have totals such as 11 or 10, and the goal is to find the minimum over all valid brackets.

Given the draw order, compute the minimum possible sum of ranking differences over all matches.

The first line contains a natural number (n). ((1 \le n \le 256))

The second line contains the rankings of the (n) players from left to right in the draw order. Each ranking is a distinct natural number between 1 and (n), inclusive.

Print the minimum possible total sum of ranking differences among all valid tournaments.