Farmer John은 친구들에게 자랑하려 전체 $N$마리, $1 \le N \le 100,000$, 번호 $1..N$을 찍으려 합니다.

촬영 당일 소들이 임의 순서 한 줄로 달려가며 $i$위치에 $c_{i}$, $1 \le c_{i} \le N$입니다. 그는 순서에 생각이 있습니다.

FJ의 생각에는 모든 $i$, $1 \le i \le N-1$에서 $i$소는 $i+1$의 왼쪽에만, $N$소는 $1$의 왼쪽에만 서야 합니다. 물론 첫, 맨 왼쪽 소의 왼쪽에는 아무도 없습니다.

촬영 후 약속한 저녁에 배고파하니 서두릅니다. 지시를 잘 못 따라 한 분에 인접 두 소를 골라 한 번 바꿉니다. 가능한 순서까지 얼마나 걸릴까요?

다섯 소의 초기 예입니다.

     왼쪽           오른쪽
        3  5  4  2  1

먼저 두 번째 쌍을 바꿉니다.

        3  4  5  2 1

다음 맨 오른쪽 쌍입니다.

        3  4  5  1  2

단 두 분의 교환으로 가능한 순서입니다.

입력

• 줄 $1$: 정수 $N$ 하나.

• 줄 $2..N+1$: 줄 $i+1$에 $i$번째 소 번호 $c_{i}$.

출력

• 줄 $1$: 적절한 순서까지 최소 분 수.

예제

입력 1

5
3
5
4
2
1

출력 1

2

참고

문제 작성자: Travis, 2010