Juggler

You are juggling several balls arranged in a circle with one hand. To finish your act, you want to drop every ball in a specified order using as few moves as possible.

On each move you may do exactly one of the following:

• rotate every ball one step counterclockwise,
• rotate every ball one step clockwise, or
• drop the ball currently in your hand.

When you drop the ball in your hand, the next ball clockwise immediately falls into your hand.

Given the order in which the balls must be dropped, find the minimum number of moves needed to drop all of them.

The input contains several test cases. Each test case begins with a line containing an integer $n$ ($1 \le n \le 100{,}000$), the number of balls being juggled.

Each of the next $n$ lines contains one integer $k_i$ ($1 \le k_i \le n$). Here $i$ is the clockwise position of a ball counting from the ball in your hand (position $1$), and $k_i$ is the order in which that ball must be dropped. The values $k_1, k_2, \ldots, k_n$ are a permutation of $1$ through $n$.

The input ends with a line containing a single $0$, which is not part of any test case.

For each test case, print a single line with one integer: the minimum number of moves needed to drop all balls in the required order.

Print no extra spaces and do not separate answers with blank lines. Every answer fits in a signed 64-bit integer.

Consider the example with three balls. The ball in your hand must be dropped third, the ball immediately clockwise must be dropped second, and the next ball clockwise must be dropped first.

Rotate one step so that the ball that must go first reaches your hand, then drop it; its clockwise neighbor immediately falls into your hand. One more rotation and two more drops finish the act, for five moves in total.