#P5133. tb148的客人

tb148的客人

题目背景

tb148使用优惠券买来了许多食材后,请来了很多客人来吃饭。

题目描述

tb148和他的n个客人,他们每人有一个编号(从一开始的连续正整数)。目前,大家不按编号,乱序围坐在一张圆桌上。每次操作我们可以同时让任意多的客人沿顺时针或逆时针移动一个位置,我们称作一次操作。这个过程中一个位置可以没有客人或有多个客人。请问最少需要多少秒,使得每个位置仍恰好只有一个数,且客人的编号沿顺时针或逆时针依次为1~n?

输入格式

输入包含两行。 第一行为一个正整数n。第二行为n 个空格隔开的正整数,为一个1~n 的排列,表 示最开始时按顺时针顺序的客人编号。

输出格式

输出一个整数表示答案。

4
1 4 2 3
1

提示

对于40% 的数据,1≤n≤3000。 对于80% 的数据,1≤n≤300000。 对于100% 的数据,1≤n≤1000000。