Hide

Problem G
Ordering Hotbar

/problems/orderinghotbar/file/statement/en/img-0001.png
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
CPU Time limit 1 second
Memory limit 1024 MB
Author
Saarthak Sharma
Source CodeSprint LA 2021
License Creative Commons License (cc by-sa)

Please log in to submit a solution to this problem

Log in