Hide

Problem G
Messy lists

Languages en sv

Doris has just started to program, and is participating in their first programming competition. She has encountered a problem that can be solved by sorting some cool integers. She decides to use the built-in sorting function in the revolutionary new programmering language Meowscript. However, the language isn’t completely finished and its sorting function seems to be a little buggy.

Help Doris determine how many elements are in the wrong index in the incorrectly sorted list of integers, compared to the same list if it had been properly sorted in increasing order.

Input

The first row contains an integer $N$ ($1\leq N \leq 10^6$), the number of elements in the list. The second row contains the $N$ integers $0\leq A_ i \leq 10^9$ that make up the incorrectly sorted list.

Output

Print one integer - the number of elements in the list that are in the wrong position.

Grading

Your solution will be tested on a number of test-case groups. To receive points for a group, your solution must correctly solve every test-case in the group.

Group

Point value

Restrictions

$1$

$20$

$N \leq 2$

$2$

$20$

The built-in sorting function sorts in decreasing order

$3$

$20$

$N \leq 1000$

$4$

$40$

No further restrictions

Sample Input 1 Sample Output 1
5
1 1 2 3 5
0
Sample Input 2 Sample Output 2
7
3 1 4 1 5 9 2
6