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

문제

You are given an array [p[1], p[2], ..., 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[1] = 2, p[2] = 3, p[3] = 1] in two operations:

  1. Swap p[1] and p[3]. The array becomes [p[1] = 1, p[2] = 3, p[3] = 2].
  2. Swap p[2] and p[3]. The array becomes [p[1] = 1, p[2] = 2, p[3] = 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[1], p[2], ..., p[n] representing the array [p[1], p[2], ..., 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