시간 제한메모리 제한제출정답맞힌 사람정답 비율
3 초 (추가 시간 없음) 1024 MB38271965.517%

## 문제

You are given an array [p, p, ..., p[n]] where all the numbers in the array are distinct. In addition, the numbers are positive integers between 1 and n. You can only perform the following operations on the array: Pick two indices x and y such that |p[x]−p[y]| = 1, and then swap the values of p[x] and p[y]. We now want to sort this array in ascending order. That is, to make p[i] = i for all i ∈ {1, 2, ..., n}. For example, we can sort the array [p = 2, p = 3, p = 1] in two operations:

1. Swap p and p. The array becomes [p = 1, p = 3, p = 2].
2. Swap p and p. The array becomes [p = 1, p = 2, p = 3] which is sorted in ascending order.

Please write a program to compute the minimum number of operations to sort a given array in ascending order.

## 입력

The input contain two lines. The first line contains one integer n. The second lines contain n space-saparated numbers p, p, ..., p[n] representing the array [p, p, ..., p[n]].

## 출력

Output only one number that denotes the minimum number of operations required to sort the given array.

## 제한

• 1 < n ≤ 200000.
• 1 ≤ p[i] ≤ n.
• All p[i] are distinct.

## 예제 입력 1

3
1 3 2


## 예제 출력 1

1


## 예제 입력 2

5
5 3 2 1 4


## 예제 출력 2

7