22856_CowSorting

Farmer John has C (2 ≤ C ≤ 400) cows and the same number of stalls. These cows are notoriously fickle about their stall arrangement.  While they enter the stalls in an order that appears to be random, they must be rearranged to be in a "proper" order or their milk output will decrease.

To find the "proper" order, each cow examines its brand (which is a positive integer smaller than 2,000,000) to ensure that the cow to her right has a brand at least as large and the cow to her left has a brand at least as small.  Interestingly, the cow with the smallest brand knows that she might also have on her left the cow with the largest brand (and, likewise, the cow with the largest brand knows she might have on her right the cow with the smallest brand).  If these ordering rules are met, the cows are in "proper" order.  Note that these ordering rules are intended to describe a cycle of a sorted list and not something exotic.

By way of example, if the cow's brands were 2, 2, 4, 5, 7, the set of proper orderings for the cows in the stalls is:

2 2 4 5 7
7 2 2 4 5
5 7 2 2 4
4 5 7 2 2
2 4 5 7 2

If you have any experience with cows, you know that moving them is difficult.  In order to rearrange the cows, Farmer John can lead cows out of stalls, traverse the stalls, and lead the cows into other stalls.

Having only two hands, FJ can lead at most two cows at a time (before having to deposit at least one cow back into some stall).

Farmer John exerts 10 joules of energy to remove a cow from a stall and 10 joules to put a cow into a stall.  He exerts 1 joule for each cow he is leading for every stall-length he walks while leading those cows. If he's not leading a cow, he exerts no energy walking by himself between stalls.

Thus, if he goes from the 3rd stall to the 7th stall leading 2 cows, he will expend (7-3)*2 = 8 joules of energy doing so.  Walking back to stall 1 while leading no cows requires 0 joules.

Determine the minimum amount of energy Farmer John must exert to put the cows into a "proper" order.

多测试用例。

* Line 1: One integer: C

* Lines 2..C+1:  Each line contains a cow brand.  The input lines are ordered such that the first brand given is in stall 1, the second in stall 2, and so on.

A single line with the integer that represents the minimum amount of energy Farmer John must exert.

5
5
2
7
4
2

66

Arrived at like this:
  Action              Cost    Stalls     FJ
Cow out of stall 1     10   * 2 7 4 2    5
Walk to stall 2         1   * 2 7 4 2    5
Cow out of stall 2     10   * * 7 4 2    5 2
Cow #5 into stall 2    10   * 5 7 4 2    2
Walk to stall 4         2   * 5 7 4 2    2
Cow out of stall 4     10   * 5 7 * 2    2 4
Cow #2 into stall 4    10   * 5 7 2 2    4
Walk to stall 1         3   * 5 7 2 2    4
Cow #4 into stall 1    10   4 5 7 2 2    -
Final configuration: 4 5 7 2 2; final cost: 66