题目描述

筝是一个喜欢音乐的女孩，她想写出优美的旋律。

筝有一段由 $n$ 个音符组成的旋律 $a_1, \ldots, a_n$，她用 $1 \sim n$ 给这些音符编号。保证 $a_1, \ldots, a_n$ 构成一个 $1$ 到 $n$ 的排列。

筝想让每段旋律都足够优美，所以她会对旋律进行若干次调整。每次调整，她会选择两种音符 $x,y$（$x,y\in[1,n]$），将旋律中所有的音符 $x$ 替换为音符 $y$。形式化地，$\forall a_i = x,a_i \gets y$。这会花费 $\lvert x-y\rvert$ 的调整度。

所有调整结束后，$\forall i\ne j$，若 $a_i = a_j$，则音符 $a_i, a_{i+1}, \ldots, a_j$ 均会产生一次共鸣。

筝认为一段旋律是优美的，当且仅当所有音符都产生至少一次共鸣。她想知道，为了将旋律调整为优美的，她花费的调整度之和最小能是多少。

输入格式

第一行包含一个正整数 $n$，表示音符数量。

第二行包含 $n$ 个正整数 $a_1, \ldots, a_n$，表示初始旋律。

输出格式

输出一行，包含一个正整数，表示调整度之和的最小值。

5
1 4 3 2 5

2

提示

【样例解释】

第一次调整：选择 $x=1,y=2$，调整度为 $1$，旋律变为 $2,4,3,2,5$。

第二次调整：选择 $x=4,y=5$，调整度为 $1$，旋律变为 $2,5,3,2,5$。

所有调整结束后，位置 $1$ 和位置 $4$ 之间的音符产生共鸣，位置 $2$ 和位置 $5$ 之间的音符产生共鸣，所有音符都至少产生一次共鸣，调整度之和为 $2$。

【数据范围】

本题采用捆绑测试。

$\text{Subtask}$	$n\le$	特殊性质	分数
$1$	$20$	无	$10$
$2$	$300$		$15$
$3$	$3000$
$4$	$10^6$	$a_i = i$	$10$
$5$		无	$30$
$6$	$10^7$		$20$

对于所有数据，保证：$2\le n\le 10^7$，且 $a_1, \ldots, a_n$ 构成一个 $1 \sim n$ 的排列。

【提示】

数据输入的规模可能较大，请选手注意输入读取方式的效率。