Submit solution

Points: 7 (partial)
Time limit: 2.0s
Memory limit: 128M

Author:
Problem type

Larry's dog Spot's toys are all over the place, and Larry is determined to put them back in order. Each of the toys is placed in a line, has an integer height, and should be sorted in increasing order. Larry broke his foot and can't walk so the only way to move the blocks is for Larry to tell Spot to fetch a toy at any index i and bring it to the front of the line. Given the list of Larry's toy's heights, determine the least number of fetches needed to sort the toys in increasing order.

Input Specification

First line: N (the number of toys that Spot has).

Second line: The heights of the toys in order of the line (guaranteed to be a permutation of the sequence 1, 2, 3, \ldots\,N).

Output Specification

One integer: the least number of fetches needed to sort the toys in increasing order.

Constraints

For all test cases: 1 \le N \le 2 \times 10^5.

For 20% of the marks: 1 \le N \le 8.

Sample Input 1:
5
2 3 4 5 1
Sample Output 1:
1

Explanation: Spot just needs to fetch the last toy, making the sequence 1 2 3 4 5.

Sample Input 2:
5
5 4 3 2 1
Sample Output 2:
4

Comments

There are no comments at the moment.