Height Checker

A line of n students is currently standing in a given order of heights. The expected order is the heights arranged in non-decreasing order. Determine how many students are NOT standing in their expected position, i.e. the number of indices i such that the current height at index i differs from the height that would be at index i if the array were sorted.

Input: The first line contains an integer n, the number of students. The second line contains n space-separated integers, the heights in the order the students are currently standing. Output: Print a single integer: the number of indices where the current height differs from the expected (sorted) height.

1 <= n <= 8000 1 <= heights[i] <= 100000

The problem never asks you to actually MOVE anyone - just to count how many are out of place - a subtle but important distinction that keeps the solution much simpler than an actual rearrangement problem would require.

Count how many students are standing out of place, compared to where they'd stand if lined up by height. Brute force: There isn't really a 'slower' meaningful alternative - sorting a copy and comparing position by position IS the direct, simplest approach; the only real cost is the sort itself. Optimised: Since you only need to COUNT disagreements (not figure out how to physically rearrange anyone), sorting a copy once and comparing it to the original in a single linear pass directly answers the question - no need for any more complex logic beyond a sort and a comparison.

1. Make a sorted COPY of the heights array - this represents the 'expected' lineup. 2. Compare the original array to this sorted copy, position by position. 3. Count every position where the two arrays disagree.

Time: O(n log n) - dominated by sorting the copy; the comparison pass itself is O(n). Space: O(n), for the sorted copy.

The array may already be fully sorted, in which case the answer is 0; every element could also be identical.

This is a great example of a problem that SOUNDS like it might need complex rearrangement logic but actually just needs a straightforward sort-and-compare - recognizing when a problem is simpler than it initially sounds is a valuable skill.