Score : 600 points
Snuke got an integer sequence of length N from his mother, as a birthday present. The i-th (1 ≦ i ≦ N) element of the sequence is a_i. The elements are pairwise distinct. He is sorting this sequence in increasing order. With supernatural power, he can perform the following two operations on the sequence in any order:
Snuke likes Operation 2, but not Operation 1. Find the minimum number of Operation 1 that he has to perform in order to sort the sequence in increasing order.
The input is given from Standard Input in the following format:
N A_1 : A_N
Print the minimum number of times Operation 1 that Snuke has to perform.
4 2 4 3 1
1
The given sequence can be sorted as follows:
In this sequence of operations, Operation 1 is performed once. It is not possible to sort the sequence with less number of Operation 1, thus the answer is 1.
5 10 8 5 3 2
0