34836번 - 꼬치

문제

꼬치에 꼬치 재료 $N$개가 일렬로 꽂혀 있다. 앞에서부터 $i$번째에 위치한 꼬치 재료의 맛은 $T_i$이며, 꼬치 재료의 맛은 1ドル$ 이상 $N$ 이하의 서로 다른 정수이다.

당신은 비어 있는 두 그릇 $A$와 $B$를 사용하여 꼬치 재료를 맛의 오름차순으로 정렬하기로 했다.

• 꼬치의 맨 앞에 꽂혀 있는 재료를 뺀 뒤, 그 재료를 그릇 $A$에 놓는다.
• 꼬치의 맨 뒤에 꽂혀 있는 재료를 뺀 뒤, 그 재료를 그릇 $B$에 놓는다.
• 그릇 $A$에 놓인 재료 중 하나를 골라 꼬치의 맨 앞에 꽂는다.
• 그릇 $B$에 놓인 재료 중 하나를 골라 꼬치의 맨 뒤에 꽂는다.

그릇에 놓인 재료가 하나라도 있다면 오름차순으로 정렬된 것이 아니다.

꼬치 재료의 맛을 오름차순으로 정렬하려면, 위 행동을 최소 몇 번 수행해야 하는지 알아내라.

입력

첫째 줄에 꼬치 재료의 개수 $N$이 주어진다. (1ドル \leq N \leq 200,000円$)

둘째 줄에 꼬치 재료의 맛 $T_1, T_2, \ldots, T_N$이 공백으로 구분되어 주어진다. $T_i$는 서로 다르다. (1ドル \leq T_i \leq N$)

출력

첫째 줄에 꼬치 재료를 맛의 오름차순으로 정렬하기 위해 필요한 행동의 최소 횟수를 출력한다.

제한

노트