407416: GYM102787 A Shandom Ruffle

Those of you who use Java (or are subscribed to SecondThread) likely know that calling Arrays.sort() on an array of primitives in Java can lead to TLE verdicts on Codeforces contests because there are some very specific cases in which quicksort runs in $$$n^2$$$ time. There are a couple solutions to this: one is to use Collections.sort() on an ArrayList. This uses mergesort and is always $$$n*log(n)$$$.

Another solution is to shandomly ruffle [aka randomly shuffle] the array before sorting so that it is very very very unlikely that it is still in some undesirable order. One way of doing this is to do the following:

shandom_ruffle(int a, int b, int[] array) {
  int bStart=b;
  while (a<bStart && b<=array.length) {
    swap(array[a], array); //swap the values at indecies a and b
    a++;
    b++;
  }
}

In Java and the psuedocode above, arrays are pass-by-reference. Suppose David starts with the array $$$[1, 2, 3, 4, ... n]$$$, and calls this method $$$n$$$ times on the array, the ith time passing in $$$a_i$$$ and $$$b_i$$$. What will the array look like after these $$$n$$$ method calls?

4
3 1
1 3
3 2
2 3

3 1 4 2 

5
4 1
5 4
3 5
4 5
5 2

1 2 5 3 4