정렬에 필요한 이동 횟수

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

요약

순열이 주어질 때, 인접한 두 원소 교환과 첫 원소와 마지막 원소 교환(한 번만 가능)으로 정렬하는 최소 횟수를 구합니다.

문제

순열이 주어진다.

이동은 다음 중 하나이다.

주어진 순열을 정렬하는 데 필요한 이동 횟수의 최솟값은 얼마인가?

첫째 줄에 순열의 길이인 정수 $n$ ( $1 \leq n \leq 3 \cdot 10^5$ )이 주어진다.

둘째 줄에 순열 자체인 정수 $a_i$ ( $1 \leq a_i \leq n$ ) $n$ 개가 주어진다.

정렬에 필요한 최소 이동 횟수를 한 줄에 출력한다.