题目描述

有 $n$ 帧胶片，按照拍摄时间编号为 $1,2,\ldots,n$。起初每一帧单独成卷，因此共有 $n$ 卷胶片，第 $i$ 卷中只有编号为 $i$ 的一帧。

如果一卷胶片中包含的帧编号恰好为 $A,A+1,\ldots,B$，其中 $1\le A\le B\le n$，则称这卷胶片覆盖编号区间 $[A,B]$。卷内各帧的先后顺序不必按照编号递增。

任意时刻，若现有两卷胶片分别覆盖相邻的编号区间 $[L,M]$ 和 $[M+1,R]$，其中 $1\le L\le M<R\le n$，就可以选择以下一种方式将它们接成一卷：

• 正向接片：先放入覆盖 $[L,M]$ 的整卷，再放入覆盖 $[M+1,R]$ 的整卷，代价为 $0$；
• 倒序接片：先放入覆盖 $[M+1,R]$ 的整卷，再放入覆盖 $[L,M]$ 的整卷，代价为 $1$。

被选择的两卷会被新卷替代，新卷覆盖 $[L,R]$，之后仍可参与接片。能否接片只由两卷覆盖的编号区间决定。每次接片都只改变两整卷的前后次序，不会翻转、打散或交错任意一卷内部的帧。

不断接片，直到只剩一卷胶片。给定 $1,2,\ldots,n$ 的一个排列 $p_1,p_2,\ldots,p_n$，你需要使最后一卷中从前到后的帧编号依次为该排列。

请计算所有可行接片过程的最小总代价。如果无法得到给定排列，输出 $-1$。

输入格式

从文件 splice.in 中读取数据。

第一行输入一个整数 $n$，表示胶片帧数。

第二行输入 $n$ 个整数 $p_1,p_2,\ldots,p_n$，表示要求的最终帧序列。

输出格式

输出到文件 splice.out 中。

输出一个整数，表示得到给定排列所需的最小总代价；如果无法得到，输出 $-1$。

样例

1
1

0

4
2 1 4 3

2

4
3 4 1 2

1

4
2 4 1 3

-1

4
1 2 4 3

1

样例解释

样例 #1 中不需要进行接片。

样例 #2 中，可以分别用一次倒序接片得到 $[2,1]$ 和 $[4,3]$，再正向接合这两卷，总代价为 $2$。最终序列中 $2,1$ 和 $4,3$ 这两个相邻位置都是编号下降的位置，而每个这样的相邻位置都必须由一次倒序接片产生，因此总代价不能小于 $2$。

样例 #3 中，先分别正向接出 $[1,2]$ 和 $[3,4]$，再用一次倒序接片将后一卷放在前面，即可得到 $[3,4,1,2]$。

样例 #4 中，考虑最后一次接片。在三个可能的分界位置中，分界后的某一侧包含的编号集合分别会出现 $\{1,3,4\}$、$\{2,4\}$ 或 $\{1,2,4\}$；它们都不是连续编号区间，因此不存在合法的最后一次接片。

样例 #5 中，最后一次接片可以在第 $1$ 帧后分开，将 $[1]$ 与 $[2,4,3]$ 正向接合；也可以在第 $2$ 帧后分开，将 $[1,2]$ 与 $[4,3]$ 正向接合。两种方式都只需用一次倒序接片得到 $[4,3]$，最小总代价为 $1$。

数据规模与约定

对于所有数据，保证：

• $1\le n\le 500$；
• $1\le p_i\le n\ (1\le i\le n)$；
• $p_1,p_2,\ldots,p_n$ 是 $1,2,\ldots,n$ 的一个排列。

本题采用子任务捆绑计分。只有通过某个子任务内的所有测试点，才能获得该子任务的分数。各子任务独立计分。

下发文件

下载三组测试数据，非真实测试数据