题号：NC209988
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
题目描述
Inaka composes music. Today's arrangement includes a chord of notes that are pairwise distinct, represented by a permutation
of integers from
to
(inclusive) denoting the notes from the lowest to the highest.
Her friend, Miyako, sneaks in and plays a trick by altering the chord with the following two operations:
- Drop-2: Take out the second highest note and move it to the lowest position, i.e. change the permutation to
.
- Invert: Take out the lowest note and move it to the highest position, i.e. change the permutation to
.
Any number of consecutive Drop-2 operations is considered a multi-drop. Miyako would like to change the permutation to an ordered permutation, , in the fewest number of multi-drops possible. Please help her find the number of multi-drops needed.
输入描述:
The first line contains an integer n () — the number of notes.
The second line contains n space-separated integers— the original permutation of notes.
The input guarantees each integer from 1 to n (inclusive) appears in the permutation exactly once.
输出描述:
Output one integer — the number of multi-drops required to change the permutation to an ordered one.
示例1
说明
An optimal solution with two multi-drops is:
- Invert, 5 times, changing the permutation to 6,2,4,5,1,3;
- Drop-2, 3 times, changing the permutation to 4,5,1,6,2,3;
- Invert, 4 times, changing the permutation to 2,3,4,5,1,6;
- Drop-2, 1 time, changing the permutation to 1,2,3,4,5,6.