### Description

Consider a binary string (b_{1}…b_{N}) with *N* binary digits. Given such a string, the matrix of Figure 1 is formed from the rotated versions of the string.

b_{1} |
b_{2} |
… | b_{N-1} |
b_{N} |

b_{2} |
b_{3} |
… | b_{N} |
b_{1} |

… | ||||

b_{N-1} |
b_{N} |
… | b_{N-3} |
b_{N-2} |

b_{N} |
b_{1} |
… | b_{N-2} |
b_{N-1} |

Figure 1. The rotated matrix

Then rows of the matrix are sorted in alphabetical order, where ‘0’ is before ‘1’. You are to write a program which, given the last column of the sorted matrix, finds the first row of the sorted matrix.

As an example, consider the string (00110). The sorted matrix is

0 | 0 | 0 | 1 | 1 |

0 | 0 | 1 | 1 | 0 |

0 | 1 | 1 | 0 | 0 |

1 | 0 | 0 | 0 | 1 |

1 | 1 | 0 | 0 | 0 |

and the corresponding last column is (1 0 0 1 0). Given this last column your program should determine the first row, which is (0 0 0 1 1).

### Input

The first line contains one integer *N* <= 3000, the number of binary digits in the binary string. The second line contains *N* integers, the binary digits in the last column from top to bottom.

### Output

The first line contains *N* integers: the binary digits in the first row from left to right.

### Sample Input

5 1 0 0 1 0

### Sample Output

0 0 0 1 1

Solution below . . .

### Solution

/* * The process of forming a matrix from rotated versions of a string, * sorting the rows, and taking the value from the right-hand column * is called a Burrows-Wheeler Transform, and is part of the * Burrows-Wheeler Data Compression Algorithm. * * This link has a discussion of the algorithm, as well as how to * invert the transform back to the sorted matrix: * * http://www.cs.princeton.edu/courses/archive/fall07/cos226/assignments/burrows.html */ import java.util.Arrays; import java.util.LinkedList; import java.util.Scanner; public class Main { static void invert(int bwtArr[]) { int i; int len = bwtArr.length; int[] lShift = new int[len]; int[] sortedBwt = bwtArr.clone(); // Index at which original string appears // in the sorted rotations list int x = 0; Arrays.sort(sortedBwt); @SuppressWarnings("unchecked") LinkedList<Integer>[] arr = new LinkedList[2]; for (int j = 0; j < arr.length; j++) { arr[j] = new LinkedList<Integer>(); } for (i = 0; i < len; i++) { arr[bwtArr[i]].addLast(i); } for (i = 0; i < len; i++) { computeLShift(arr, sortedBwt, i, lShift); } // Decodes the BWT for (i = 0; i < len; i++) { x = lShift[x]; System.out.print(bwtArr[x] + " "); } } static void computeLShift(LinkedList<Integer>[] arr, int[] sortedBwt, int index, int[] lShift) { LinkedList<Integer> head = arr[sortedBwt[index]]; lShift[index] = head.getFirst(); head.removeFirst(); } public static void main(String[] args) { Scanner sc = new Scanner(System.in); int N = sc.nextInt(); int[] bwtArr = new int[N]; for (int i = 0; i < N; i++) { bwtArr[i] = sc.nextInt(); } sc.close(); invert(bwtArr); } }