아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

Moves You Need to Make

면접 대비

시간 제한2초메모리 제한512 MB

요약

순열이 주어질 때, 첫째와 마지막 원소를 최대 한 번 교환할 수 있다는 조건에서 정렬에 필요한 인접 교환의 최소 횟수를 구한다.

난이도: 보통10점 중 5점
유형: 배열, 정렬, 그리디
정답자: 아직 제출이 없습니다

문제

You are given a permutation.

A move is one of the following:

Swap two adjacent elements.
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.

예제12

예제 1
입력
```
1
1
```
예상 출력
```
0
```
예제 2
입력
```
2
1 2
```
예상 출력
```
0
```
예제 3
입력
```
3
3 2 1
```
예상 출력
```
1
```
예제 4
입력
```
4
4 2 1 3
```
예상 출력
```
2
```
예제 5
입력
```
5
4 1 5 3 2
```
예상 출력
```
4
```
예제 6
입력
```
6
1 5 3 4 2 6
```
예상 출력
```
5
```
예제 7
입력
```
7
3 2 1 7 6 5 4
```
예상 출력
```
9
```
예제 8
입력
```
8
4 2 6 1 5 3 7 8
```
예상 출력
```
8
```
예제 9
입력
```
9
9 8 7 6 5 4 3 2 1
```
예상 출력
```
22
```
예제 10
입력
```
10
8 2 9 5 1 7 10 4 6 3
```
예상 출력
```
17
```
예제 11
입력
```
11
7 2 3 9 11 1 8 6 4 10 5
```
예상 출력
```
23
```
예제 12
입력
```
12
3 10 6 2 4 12 7 8 5 1 11 9
```
예상 출력
```
18
```