‹ 上一题下一题 ›

s02197. 翻转排序未做

1000 ms 256 MB 测试点 10 S-14·搜索进阶 S·算法自拟题 S-14 搜索的剪枝优化迭代加深搜索

文件读写输入s02197.in输出s02197.out

题目描述

给一个 $1 \sim n$ 的排列，每次操作可以翻转任意一段连续区间（把第 $l$ 到第 $r$ 个数原地倒序）。求把它变成 $1, 2, \dots, n$ 所需的最少翻转次数。数据保证最少次数不超过 5。

输入格式

第一行一个整数 $n$ 。第二行 $n$ 个整数，是 $1 \sim n$ 的一个排列。

输出格式

一行一个整数，最少翻转次数。

样例

输入

4
2 1 4 3

输出

数据范围

对于 30% 的数据： $n \leq 5$ ，最少次数不超过 2
对于 60% 的数据： $n \leq 6$ ，最少次数不超过 3
对于 100% 的数据： $n \leq 8$ ，最少次数不超过 5

输入

输出

答案