有趣的排序

import java.util.Arrays;
import java.util.Scanner;
public class Main4 {
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		int n=sc.nextInt();
		int[] in=new int[n];
		for(int i=0;i<n;i++) 
			in[i]=sc.nextInt();
		int[] in2=in.clone();
		Arrays.sort(in2);
		int count=0;
		for(int i=0;i<n;i++)
			if(in[i]==in2[count]) 
				count++;
		System.out.println(n-count);
	}
}

	// 只需要扫描2遍就能完成



	// 交换发生的情况应该是：



	// 如果当前数之后有比自己小的数，说明当前数是逆序数，这个时候需要把当前数扔到末尾，操作次数+1；



	// 另外一种情况是虽然当前数不是逆序数， 但是前面有逆序数比自身小，那么操作次数也需要+1，因为之前的逆序数被扔到后面去了



	// 之后，当前数肯定要被扔一次。



	 
	

		import java.util.*;
	

	

		import java.io.*;
	

	

		 
	

	

		public class Main {   
	

	

		    public static void main(String[] args) {
	

	

		        Scanner scan = new Scanner(System.in);
	

	

		        int count = scan.nextInt();       
	

	

		        if(count < 0) {
	

	

		            return;
	

	

		        }
	

	

		        inti = 0;
	

	

		        int[] nums = new int[count];
	

	

		        while(scan.hasNextInt() && i < count) {
	

	

		            nums[i] = scan.nextInt();
	

	

		            ++i;
	

	

		        }
	

	

		        scan.close();
	

	

		        
	

	

		//为了快速判断后面是否有比自己小的数，使用了一个栈保存从后往前，
	

	

		//到每一个位置的最小值，这样可以快速判断逆序数。这里遍历了一遍
	

	

		        int res = 0;
	

	

		        Stack<Integer> reverMin = newStack<Integer>();
	

	

		        reverMin.push(nums[count-1]);       
	

	

		        i = count - 2;
	

	

		        for(; i > 0; --i) {
	

	

		            if(nums[i] < reverMin.peek()) {
	

	

		                reverMin.push(nums[i]);
	

	

		            }
	

	

		            else{
	

	

		                reverMin.push(reverMin.peek());
	

	

		            }
	

	

		        }
	

	

		        //逆序或者前面有小于自身的逆序数
	

	

		        int min = Integer.MAX_VALUE;
	

	

		        for(i = 0; i < count; ++i) {
	

	

		            if(!reverMin.empty() && nums[i] > reverMin.pop()) {
	

	

		                ++res;
	

	

		                min = Math.min(min, nums[i]);
	

	

		                continue;
	

	

		            }
	

	

		            if(nums[i] > min) {
	

	

		                ++res;
	

	

		            }           
	

	

		        }
	

	

		         
	

	

		        System.out.println(res);
	

	

		    }
	

	

		}