提示: 欢迎访问OurACM平台。
Problem 1644 Oaiei's cube III

Accept: 50    Submit: 163
Time Limit: 3000 mSec    Memory Limit : 65536 KB

Problem Description

Oaiei recently thinks about a problem: He labels his N cubes from 1 to N and puts the N cubes into a box. Now he randomly gets the cube from the box and arranges the cube in a line according the order of removal. But the unordered cubes are uncomfortable. So he wants to arrange the unordered sequence into an ascending sequence. Every time oaiei can only exchange two cubes and he can exchange two cubes arbitrarily. Now, your task is using the minimum movement to arrange the unordered sequence into an ascending sequence.

Input

There are multiple test cases. For each test case, there is an integer N, denoting oaiei has N cubes (1<=N<=10000000). Followed N different numbers, the numbers are labeled between 1 to N.

Output

For each test case, you should output he minimum movement.

Sample Input

3 3 2 1

Sample Output

1

Source

FZU 2008 Summer Training II--Combinatorics

Submit  Back  Status  Discuss