P5133 Guests of tb148

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

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$.

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 one integer, the answer.

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