Skip to main content

Contest 2 — B: Balloon Heights

Challenge on lesson: Contest 2-B: Balloon Heights

CHALLENGE
Difficulty: intermediate+25 XP

**Description:** n balloons float at distinct heights. You may swap any two balloons' positions. Find the minimum number of swaps so the heights end in strictly increasing order. Heights are a permutation of distinct values — map them to ranks 1..n first. **Input:** Line 1: n (1 <= n <= 100000). Line 2: n distinct integers (|h[i]| <= 10^9). **Output:** One integer — the minimum number of swaps. **Example:** 4 / 4 3 2 1 -> 2 (swap 4<->1, swap 3<->2).

Back to lesson: Contest 2-B: Balloon Heights