You are given an array $a$ of length $n$. You should sort the array in increasing order by performing the following operation: picking two of its elements and swap them. Find an optimal way to sort the array.

Input

The first line contains a single integer $n$. The next line contains $n$ integers $a_1,\,a_2,\dots,\,a_n$.

Output

Print the minimum number of operations required to sort the array.

Constraints

• $1 \leq n \leq 10^5$
• $1 \leq a_i \leq 10^9$
• $a_i \neq a_j$ if $i \neq j$

Example 1

Input:

5
1 11 9 19 4

Output:

2

Example 2

Input:

10
18 13 20 12 4 5 19 15 14 11

Output:

7