Description

You are the leader of a swarm of $n$ sharks living in a one-dimensional ocean. The sharks are positioned from left to right, with each adjacent pair separated by a distance of one unit.

As the leader, you want all the sharks to gather at a common point to form a single group. Initially, no two sharks belong to the same group; for each $i = 1, \ldots, n$, the $i$-th shark from the left forms its own group, uniquely numbered $a_i$, consisting of only itself.

To achieve your goal, you can command the sharks to perform the following actions $n - 1$ times.

1. You shout out an integer $b$ that meets both conditions:
   • There exists a group numbered $b$.
   • There exists at least one group numbered strictly smaller than $b$.
2. Afterward, letting $c$ be the largest existing group number strictly smaller than $b$, all the sharks in the group numbered $b$ simultaneously move to the position of the group numbered $c$, and the two groups merge.
3. The merged group is numbered $b$, and the group numbered $c$ ceases to exist.

All sharks move at a constant speed of one unit distance per unit time. Commands must be executed sequentially, with no overlap in execution. Once a command is completed, the next one can begin immediately.

Compute the minimum time required for all the sharks to gather at a common point by commanding the sharks $n - 1$ times optimally.

Input Format

The first line of input contains an integer $n$ ($2 \leq n \leq 500$). The second line contains $n$ pairwise distinct integers $a_1, a_2, \ldots, a_n$ ($1 \leq a_i \leq n$).

Output Format

Output the minimum time required for all the sharks to gather at a common point.

4
3 2 4 1

4

9
1 2 4 5 7 8 3 6 9

17

Hint

Explanation for the sample input/output #1

You can command the sharks to perform the following actions:

1. You shout out $3$. The leftmost shark moves to the position of the second-leftmost shark, and they form a group numbered $3$. This takes $1$ unit of time.
2. You shout out $4$. The second rightmost shark moves to the position of the group numbered $3$, and they form a group numbered $4$. This takes $1$ unit of time.
3. You shout out $4$. The sharks in the group numbered $4$ move to the rightmost position, forming a group of four sharks. This takes $2$ units of time.

The total time is $1 + 1 + 2 = 4$. It can be shown that $4$ units of time is optimal.