AtCoder 图片原名已被搁置;此后,原始图像取自英语原文,现已完整保存。 给出

可复制的 PDF 提取文本
Gennady Korotkevich Contest 1
Petrozavodsk Training Camp, Day 1, Friday, August 23, 2013
Problem G. Gowk's Errand for Master
Input le: gem.in
Output le: gem.out
Time limit: 2 seconds
Memory limit: 256 megabytes
Do you think that sorting is easy? This is not the case when you're running out of time.
Unexpected weird things often happen in our life. For example, now you have array A and you
need to sort it in non-decreasing order. The problem is that you don't really have time to do that.
Fortunately, your friend is very good at sorting arrays, so you decided to ask for his help. You
believe that your friend's special abilities are due to his very conceptual approach. In one second
he takes an element out of the array and places it either at the beginning or the end of the array.
For example, if the array is 4 2 5 6 1 3, then taking out 5 and placing it at the beginning would
yield 5 4 2 6 1 3, while taking out 2 and placing it at the end would yield 4 5 6 1 3 2.
Of course, your friend does everything as fast as possible, because he doesn't want to waste his
time. The only thing you want to know is how much time you have for doing other useful things
while your array is being sorted.
Input
The rst line of the input le contains N the number of elements in A (1 ≤N ≤3 · 105). The
second line contains N integer numbers Ai (1 ≤Ai ≤106).
Output
Output the sought minimum time needed for your friend to sort A, in seconds.
Examples
gem.in gem.out
5 2
2 5 1 3 3
4 1
1 2 2 1
Note
Your friend will sort the array from the rst example test case in two seconds: he'll rst move 1
to the beginning to yield 1 2 5 3 3, and then he'll move 5 to the end to yield 1 2 3 3 5.
Page 7 of 10