Problem G
Ordering Hotbar
Dan is an epic gamer attempting his longest speedrun yet.
Before he makes his attempt, he wants to organize his hotbar so
that it is easier to use. The hotbar is a list of items that
are usually displayed on the bottom of the screen that are
available to the player to use throughout the game. He wants to
sort the items in his hotbar according to how useful they are.
He wants the most useful items on the right where he can
quickly access them, and the least useful ones on the
left.
Given an array $a$ of $n$ integers representing the utility of each item in the hotbar, sort the items in increasing order using the allowed moves. You are allowed to remove an item from the list and place it at either end of the list (before the first item or after the last one). After moving an item to an end, the items in the list shift to fill the open space from where the item was removed. Find the least number of moves needed to sort the items. You may assume that all the items in the array are unique.
Input
The first line consists of an integer $1\leq n \leq 100\, 000$, giving the number of spaces in the hotbar. The second line contains $n$ space-separated integers, each between $0$ and $1\, 000\, 000\, 000$, representing the utility of each item in the hotbar in the order that they are present.
Output
Output one line containing a single number, the number of moves needed to sort the hotbar.
| Sample Input 1 | Sample Output 1 |
|---|---|
6 15 7 9 16 3 1 |
4 |
