시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 2048 MB232323100.000%

문제

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, \dots , 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.

입력

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

출력

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

예제 입력 1

4
3 2 4 1

예제 출력 1

4

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.

예제 입력 2

9
1 2 4 5 7 8 3 6 9

예제 출력 2

17