P15501 [ICPC 2025 APC] Gathering Sharks

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.

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 the minimum time required for all the sharks to gather at a common point.

**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.