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