시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 (추가 시간 없음) 512 MB222100.000%

문제

You are given a permutation.

A move is one of the following:

  1. Swap two adjacent elements.
  2. Swap the first and the last elements. Can be used at most once.

What is the minimum number of moves you need to make to sort the given permutation?

입력

The first line contains a single integer $n$ ($1 \leq n \leq 3 \cdot 10^5$), the length of the permutation.

The second line contains $n$ integers $a_i$ ($1 \leq a_i \leq n$), the permutation itself. 

출력

Output a single integer --- the minimum number of moves you need to make to sort the given permutation.

예제 입력 1

1
1

예제 출력 1

0

예제 입력 2

2
1 2

예제 출력 2

0

예제 입력 3

3
3 2 1

예제 출력 3

1

예제 입력 4

4
4 2 1 3

예제 출력 4

2

예제 입력 5

5
4 1 5 3 2

예제 출력 5

4

예제 입력 6

6
1 5 3 4 2 6

예제 출력 6

5

예제 입력 7

7
3 2 1 7 6 5 4

예제 출력 7

9

예제 입력 8

8
4 2 6 1 5 3 7 8

예제 출력 8

8

예제 입력 9

9
9 8 7 6 5 4 3 2 1

예제 출력 9

22

예제 입력 10

10
8 2 9 5 1 7 10 4 6 3

예제 출력 10

17

예제 입력 11

11
7 2 3 9 11 1 8 6 4 10 5

예제 출력 11

23

예제 입력 12

12
3 10 6 2 4 12 7 8 5 1 11 9

예제 출력 12

18