시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 1024 MB | 27 | 13 | 12 | 48.000% |
Arup has just created a data structure that makes the two following list transformations in constant O(1) time:
You've realized that sorting speed can be improved using these transformations. For example, consider the input list:
We can do the following sequence of transformations to sort this list:
You are now curious. Given an input array of distinct values, what is the fewest number of these first/last operations necessary to sort the array?
Given an initial permutation of the integers 1, 2, ..., n, determine the fewest number of first/last operations necessary to get the list of values sorted in increasing order.
The first line of input will contain a single positive integer, n (n ≤ 105), representing the number of values to be sorted. The next n lines contain one integer each. All of these integers will be distinct values in between 1 and n (inclusive), representing the original order of the data to sort for the input case.
On a line by itself, output the fewest number of first/last operations necessary to sort the input list.
8 8 3 6 7 4 1 5 2
5
5 1 2 5 3 4
1