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.


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 one line containing a single number, the number of moves needed to sort the hotbar.

Sample Input 1 Sample Output 1
15 7 9 16 3 1 

Please log in to submit a solution to this problem

Log in