该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Rotate

题目背景

在 $c++$ 中有一个函数叫 $rotate$ ，内容如下：

$rotate(\,first,\,middle,\,last\,)$

功能是将一个序列中的 $[\, first,\quad middle\,)$ 和 $[\, middle,\quad last\, )$ 部分互换。

例如对于序列

$v[\,\,\,]= \{ 1\, 2\, 3\, 4\, 5 \}$ ，进行操作 $rotate(\, v,\, v+2,\, v+5)$ ，会得到：$v[\,\,\,]= \{ 3\, 4\, 5\, 1\, 2 \}$。

题目内容

现给定一个由 $1 \sim n$ 组成的序列，请问最少需要多少次 $rotate$ 操作才能将给定序列转换为 $\{ 1,2,3,……，n\}$ 。

输入格式

第一行一个整数 $n$ ，表示序列长度。

第二行 $n$ 个整数，表示给定序列。

输出格式

一个整数，表示需要的最少操作数。

测试样例

输入

8
8 1 3 5 2 6 4 7

输出

3

数据范围

$1<n\leq 2e6$