Given a line of soldiers, determine the minimum number of swaps needed to move the tallest soldier to the front and the shortest soldier to the back.
Arrival of the General
A general inspects a line of soldiers. Each soldier has a distinct height.
You are given the soldiers' heights in their current order. In one move, the general may swap two adjacent soldiers.
Your task is to find the minimum number of adjacent swaps needed so that:
- the tallest soldier ends up in the first position, and
- the shortest soldier ends up in the last position.
If there are multiple soldiers with the same tallest or shortest height, only one such soldier needs to be moved accordingly. However, for this problem the heights are distinct.
Input Format
- The first line contains an integer — the number of soldiers.
- The second line contains distinct integers describing the soldiers' heights from left to right.
Output Format
- Print a single integer: the minimum number of adjacent swaps required.
Constraints
- All heights are distinct
- Heights are positive integers
Hints
- Find the positions of the minimum and maximum elements first.
- Moving the tallest soldier to the front may affect the position of the shortest soldier if the tallest soldier was originally before it.
Input Format
- Integer .
- Array of distinct heights.
Output Format
- A single integer: the minimum number of adjacent swaps needed.
Constraints
- All heights are distinct
- Heights are positive integers
Example 1
Input
5 2 1 5 3 4
Output
3
Explanation
The tallest soldier (5) is at index 3, so it takes 2 swaps to move it to the front. The shortest soldier (1) is at index 2, so after moving 5, it takes 1 more swap to move 1 to the end. Total = 3.
Example 2
Input
4 4 3 2 1
Output
0
Explanation
The tallest soldier is already at the front and the shortest soldier is already at the end.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.