There is a container that is open from both ends and is always sorted. To insert an element, its position is determined, then each of the elements to the left or to the right of that position is removed. The new element is inserted, then the removed elements are added back. Each removal or insertion is an operation. Determine the minimum number of operations after inserting a list of integers into an empty list.

Input

The first line contains number n (1 ≤ n ≤ 106). The next line contains n integers in the range from 1 to 106.

Output

Print the minimum number of operations to create the sorted list.