Migrated from Lutece 1523 我想上厕所

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

正如地球上有三种性别的人（男、女、秀吉），需要三种厕所。EX星也是，这里有n个性别，每个性别对应一个厕所，性别i对应厕所i。

现在所有的n种厕所按1、2、3……n的顺序围成一个圈（每种一个），每个厕所都有一个人（保证n个性别的人都正好有一个），每个厕所只能一个人用，有些人上对了厕所，有些人上错了厕所。

你的任务是让每个人都上对厕所，你只可以交换相邻厕所（i号厕所和i+1号、1号和n号）位置的人，问题是你最少需要进行多少次这样的操作。

保证最多只有3个人上错厕所。

Input

第一行一个整数$n(1 \leq n \leq 233)$，表示厕所个数。接下来一行有n个整数表示第i号厕所的人的性别。

Output

每组数据输出一行表示最少操作数。

Samples

1
1

0

4
4 2 3 1

1

5
2 4 3 1 5

4

Resources

第八届ACM趣味程序设计竞赛第二场（正式赛）