Door to Secret

Time Limit: 1 Second    Memory Limit: 32768 KB

An expedition was exploring an ancient ruin. They met a closed door and believed there might be some secrets behind. But the door seemed to be sealed by some ancient magic and immune to physical action. The explorers tried their best to open it: They smashed the door with hammer, burnt it with fire, shot it with gun, all of which, of course, turned out to be a waste of time.

They were just about to give up, when one of them spotted something special. "Look, what is this?" he yelled. There was a line of white stones on the ground. On the top of those stones, some strange symbols were engraved. There was an archaeologist among the explorers, who was an expert of this ancient civilization. Reading the symbols, he claimed that the stones were the key to this door. He knocked on the stones one by one; each gave a different tone. The archaeologist continued with his research. Then he found out that they should knock the stones in two passes. The former was from left to right, starting from the leftmost stone; the latter from right to left, starting from the rightmost stone. Every stone should be knocked exactly once. If they could keep the sum of tone difference between two consecutive knocks as small as possible, the door would open. Now it is your task. Given the tones of all the stones, find out the minimum sum of tone difference.

Notice that the first knock of second pass and the last knock of first pass are also considered to be consecutive.

Input

Input contains multiple test cases. The first line of each test case is a positive integer n (2 <= n <= 100) - the number of stones. The second line contains n positive integer - the tone of each stone.

The last test case is followed by a zero.

Output

For each test case, print a single line with the minimum sum of tone difference mentioned in the problem.

Sample Input

5
1 2 3 4 5
0

Sample Output

4

Submit

Source: Zhejiang University Local Contest 2004