tyEyyu53的代价游戏

题目描述

tyEyyu53有有一个数组 $a$，数组 $a$ 是数 n 的排列。由于tyEyyu53有强迫症，所以他想将数组变为递增数组，已知花费 $1$ 金币的代价可将数组中的任意一个整数移动到另外两个位置相邻的整数之中形成新的数组，要想使数组变为递增数组，所需要花费的金币代价最少为多少？

排列： $1$ 到 $n$ 中的每个整数均只出现过一次且没有 $1$ 到 $n$ 以外的整数的数组称之为 $n$ 的排序。例： $1,3,2$ 是 $3$ 的排序。 $1,3,4$ 不是 $3$ 的排序，因为 $4$ 不在 $1$ 到 $3$ 之间。 $1,1,2$ 不是 $3$ 的排序，因为 $1$ 出现了两次。

输入格式

输入有两行

第一行 $n(1 \leq n \leq 10^5)$ 表示数组中共有多少个整数

第二行共 $n$ 个整数（包含着 $1$ 到 $n$ 中的所有整数），每两个整数之间用空格隔开。

输出格式

输出仅一行，输出要想使数组变为递增数组，所需要花费的金币代价最少为多少？

样例 #1

样例输入 #1

9
1 3 5 7 4 2 6 9 8

样例输出 #1

4

提示

对于样例，第一次将 $2$ 移动到 $1$ 和 $3$ 之间形成新数组 1,2,3,5,7,4,6,9,8。第二次将 $4$ 移动到 $3$ 和 $5$ 之间形成新数组 1,2,3,4,5,7,6,9,8。第三次将 $6$ 移动到 $5$ 和 $7$ 之间形成新数组 1,2,3,4,5,6,7,9,8。第四次将 $8$ 移动到 $7$ 和 $9$ 之间形成新数组 1,2,3,4,5,6,7,8,9。总代价是 $4$。