НЖМД (하드디스크)

면접 대비

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

요약

디스크 회전 방향으로 놓인 블록 번호가 주어질 때, 1번부터 n번 블록까지 순서대로 읽는 데 필요한 최소 회전 수를 구합니다.

난이도: 쉬움10점 중 3점
유형: 배열, 구현
정답자: 아직 제출이 없습니다

문제

하드디스크(НЖМД)에는 아주 중요한 큰 파일이 하나 저장되어 있다. 파일은 같은 크기의 블록으로 나뉘어 있고, 블록들은 순서대로 놓여 있지 않고 디스크 여러 곳에 흩어져 있다. 이를 조각화(fragmentation)라고 한다. 지금 이 파일이 디스크 전체를 차지하고 있지만, 블록들은 연속해서 저장되어 있지 않다.

읽기 헤드는 디스크 위를 움직이며 데이터를 읽는다. 헤드는 디스크가 도는 방향과 같은 방향으로만 움직인다. 블록은 파일을 이루는 순서대로만 읽을 수 있다. 먼저 첫 번째 블록 위치로 헤드를 옮겨 읽고, 다음으로 두 번째 블록 위치로 옮겨 읽는 식이다. 그래서 한 바퀴만으로는 파일 전체를 읽지 못할 수도 있다.

헤드는 처음에 첫 번째 블록 앞에 있다. 헤드가 $n$ 번째 블록과 첫 번째 블록 사이를 지나갈 때마다 한 바퀴를 돈 것으로 센다. 헤드가 첫 번째 블록부터 마지막 블록까지 파일을 읽기 위해 돌아야 하는 완전 회전 수의 최솟값을 구하라.

입력

첫 줄에 블록의 개수를 나타내는 자연수 $n$ ( $1 \le n \le 10^5$ )이 주어진다. 둘째 줄에는 $1$ 부터 $n$ 까지의 수를 한 번씩 담은 순열을 이루는 서로 다른 자연수 $n$ 개 $p_i$ ( $1 \le p_i \le n$ )가 주어진다. $p_i$ 는 디스크가 도는 방향으로 $i$ 번째 자리에 저장된 블록의 번호이다.

출력

헤드가 첫 번째 블록부터 마지막 블록까지 파일 전체를 읽기 위해 필요한 완전 회전 수의 최솟값을 정수 하나로 출력한다.

예제3

예제 1
입력
```
3
3 1 2
```
예상 출력
```
1
```
예제 2
입력
```
2
1 2
```
예상 출력
```
0
```
예제 3
입력
```
4
4 3 2 1
```
예상 출력
```
3
```