34611번 - 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, \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.

제한

노트