**Solution Notes:** Many students used the obvious approach of
looping over each of the K ranges, incrementing the array elements in
each one. Unfortunately, this is much too slow to run in time on
large input cases, so we need to be a bit more clever. As it turns
out, it is easy to "implicitly" increment a range without actually
looping over all its elements and incrementing them all explicitly. To
do this, we keep track of the differences between consecutive
elements, instead of the values of the elements themselves. When we
increment a range, this only changes two differences -- one at each
endpoint of the range. Furthermore, given the differences between
consecutive elements, we can rebuild the actual array by scanning
through it sequentially and keeping a running sum of all the
differences so far. The entire algorithm runs in just O(N+K) time,
followed by an O(N log N) sort (there are even fancier algorithms
for computing the median of an array in O(N) time without needing
to sort, but those are not necessary to obtain full marks for this
problem).

```
import java.util.*;
import java.io.*;
import java.awt.Point;
import static java.lang.Math.*;
public class stacking {
public static int i(String s) { return Integer.parseInt(s); }
public static void main(String[] args) throws Exception {
BufferedReader in = new BufferedReader(new FileReader("stacking.in"));
PrintWriter out = new PrintWriter(new BufferedWriter(new FileWriter("stacking.out")));
String[] arr = in.readLine().split(" ");
int n = i(arr[0]);
int k = i(arr[1]);
int[] diff = new int[n+1];
for(int i=0; i<k; i++) {
arr = in.readLine().split(" ");
int A = i(arr[0])-1;
int B = i(arr[1])-1;
diff[A]++;
diff[B+1]--;
}
int[] data = new int[n];
int val = 0;
for(int i=0; i<n; i++) {
val += diff[i];
data[i] = val;
}
Arrays.sort(data);
out.println(data[n/2]);
out.flush();
}
}
```