Processing math: 100%
(Analysis by Nick Wu)

In this problem, we're given a list of N integers, with the guarantee that removing exactly one of them can result in a sorted array.

Because removing one of them can result in a sorted array, if we consider the elements that are not in the right order, those must form a sequence that is almost sorted, except that either the minimum element is in the rightmost slot or the maximum element is in the leftmost slot. Consequently, if there are K elements that are out of order, it will take K1 swaps to fix them, since every swap except for the last one can only fix the location of one such element.

import java.io.*;
import java.util.*;
public class outofplace {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new FileReader("outofplace.in"));
		PrintWriter pw = new PrintWriter(new BufferedWriter(new FileWriter("outofplace.out")));

		int n = Integer.parseInt(br.readLine());
		int[] height = new int[n];
		int[] sorted = new int[n];
		for(int i = 0; i < n; i++) {
			height[i] = Integer.parseInt(br.readLine());
			sorted[i] = height[i];
		}
		Arrays.sort(sorted);
		int swaps = -1;
		for(int a = 0; a < n; a++) {
			if(sorted[a] != height[a]) {
				swaps++;
			}
		}
		swaps = Math.max(0, swaps);
		pw.println(swaps);
		pw.close();
	}
	
}