A choir director lines up n singers along a single row of risers before a performance. For the photograph to look right, the row should read as non-decreasing height from one end to the other, with ties (singers of equal height) allowed to appear in either order. You are given the heights of the singers exactly as they are currently standing, from one end of the row to the other. Determine how many singers are currently NOT standing in the position that a properly height-sorted (non-decreasing) row of the very same heights would place them in — that is, count the indices where the current lineup differs from what a fully sorted arrangement of the same multiset of heights would look like at that spot.
n.n space-separated integers, the singers' heights in their current standing order.Print a single integer: the number of positions at which the current lineup differs from the non-decreasing sorted arrangement of the same heights.
1 <= n <= 1000001 <= height[i] <= 100000Example 1
Input
6 1 1 4 2 1 3
Expected
3
Explanation
The current row is [1,1,4,2,1,3]; sorted non-decreasing it would be [1,1,1,2,3,4]. Comparing position by position: (1,1) match, (1,1) match, (4,1) mismatch, (2,2) match, (1,3) mismatch, (3,4) mismatch. That is 3 mismatched positions.
Example 2
Input
5 5 1 2 3 4
Expected
5
Explanation
The current row is [5,1,2,3,4]; sorted non-decreasing it would be [1,2,3,4,5]. Every position differs (5≠1, 1≠2, 2≠3, 3≠4, 4≠5), giving 5 mismatched positions.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →