ReverseSort

면접 대비

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

요약

1부터 N까지의 순열이 주어질 때, 오름차순으로 정렬하는 데 필요한 부분 배열 뒤집기 연산의 최솟값을 구한다.

난이도: 보통10점 중 5점
유형: BFS, 완전 탐색, 정렬, 해시맵
정답자: 아직 제출이 없습니다

문제

1부터 N까지의 N개 숫자로 이루어진 순열 A1, A2, ..., AN이 주어진다. 이 순열에 대해 구간 [i, j] (1 ≤ i ≤ j ≤ N)의 숫자 순서를 뒤집는 연산 reverse(i, j)를 할 수 있다. 예를 들어 [1, 2, 3, 4, 5]에 reverse(2, 4)를 적용하면 [1, 4, 3, 2, 5]가 된다. 순열을 오름차순으로 정렬하는 데 필요한 최소 연산 횟수를 구하시오.

입력

입력은 다음 형식으로 주어진다.

N
A1 A2 ... AN

출력

문제의 답을 한 줄에 출력한다.

제한

N은 정수이다.
2 ≤ N ≤ 10

예제4

예제 1
입력
```
5
1 4 3 5 2
```
예상 출력
```
2
```
예제 2
입력
```
5
3 1 5 2 4
```
예상 출력
```
4
```
예제 3
입력
```
3
1 2 3
```
예상 출력
```
0
```
예제 4
입력
```
10
3 1 5 2 7 4 9 6 10 8
```
예상 출력
```
9
```