Background

After tb148 bought a lot of ingredients using coupons, he invited many guests to have a meal.

Problem Description

tb148 and his $n$ guests each have an ID number (consecutive positive integers starting from $1$). Currently, they are sitting around a round table in a random order, not by their IDs. In one operation, we may simultaneously let any number of guests move one position clockwise or counterclockwise; we call this one operation. During this process, a position may have no guest or multiple guests. Find the minimum number of seconds needed so that each position still has exactly one person, and the guests' IDs in clockwise order (or in counterclockwise order) are exactly $1 \sim n$.

Input Format

The input contains two lines.

The first line is a positive integer $n$.

The second line contains $n$ space-separated positive integers, a permutation of $1 \sim n$, representing the guests' IDs in clockwise order at the beginning.

Output Format

Output one integer, the answer.

4
1 4 2 3

1

Hint

For $40\%$ of the testdata, $1 \le n \le 3 \times 10^3$.

For $80\%$ of the testdata, $1 \le n \le 3 \times 10^5$.

For $100\%$ of the testdata, $1 \le n \le 10^6$.

Translated by ChatGPT 5