Time Limit: Java: 2000 ms / Others: 2000 ms

Memory Limit: Java: 65536 KB / Others: 65536 KB

Let { A1,A2,...,An } be a permutation of the set{ 1,2,..., n}. If i Aj then the pair (Ai,Aj) is called an "inversion" of the permutation. For example, the permutation {3, 1, 4, 2} has three inversions: (3,1), (3,2) and (4,2).

The inversion table B1,B2,...,Bn of the permutation { A1,A2,...,An } is obtained by letting Bj be the number of elements to the left of j that are greater than j. (In other words, Bj is the number of inversions whose second component is j.) For example, the permutation:

{ 5,9,1,8,2,6,4,7,3 }

has the inversion table

2 3 6 4 0 2 2 1 0

since there are 2 numbers, 5 and 9, to the left of 1; 3 numbers, 5, 9 and 8, to the left of 2; etc.

Perhaps the most important fact about inversions is Marshall Hall's observation that an inversion table uniquely determines the corresponding permutation. So your task is to convert a permutation to its inversion table, or vise versa, to convert from an inversion table to the corresponding permutation.

The inversion table B1,B2,...,Bn of the permutation { A1,A2,...,An } is obtained by letting Bj be the number of elements to the left of j that are greater than j. (In other words, Bj is the number of inversions whose second component is j.) For example, the permutation:

{ 5,9,1,8,2,6,4,7,3 }

has the inversion table

2 3 6 4 0 2 2 1 0

since there are 2 numbers, 5 and 9, to the left of 1; 3 numbers, 5, 9 and 8, to the left of 2; etc.

Perhaps the most important fact about inversions is Marshall Hall's observation that an inversion table uniquely determines the corresponding permutation. So your task is to convert a permutation to its inversion table, or vise versa, to convert from an inversion table to the corresponding permutation.

The input consists of several test cases. Each test case contains two lines.

The first line contains a single integer N ( 1 <= N <= 50) which indicates the number of elements in the permutation/invertion table.

The second line begins with a single charactor either 'P', meaning that the next N integers form a permutation, or 'I', meaning that the next N integers form an inversion table.

Following are N integers, separated by spaces. The input is terminated by a line contains N=0.

The first line contains a single integer N ( 1 <= N <= 50) which indicates the number of elements in the permutation/invertion table.

The second line begins with a single charactor either 'P', meaning that the next N integers form a permutation, or 'I', meaning that the next N integers form an inversion table.

Following are N integers, separated by spaces. The input is terminated by a line contains N=0.

提交代码