Let S = s1 s2 ... s2n be a well-formed string of parentheses. S can be encoded in two different ways:

• By an integer sequence P = p1 p2 ... pn where pi is the number of left parentheses before the ith right parenthesis in S (P-sequence).
• By an integer sequence W = w1 w2 ... wn where for each right parenthesis, say a in S, we associate an integer which is the number of right parentheses counting from the matched left parenthesis of a up to a. (W-sequence).

Following is an example of the above encodings:

S (((()()())))
P-sequence 4 5 6666
W-sequence 1 1 1456

Write a program to convert P-sequence of a well-formed string to the W-sequence of the same string.

Input

The first line of the input contains a single integer t (1 <= t <= 10), the number of test cases, followed by the input data for each test case. The first line of each test case is an integer n (1 <= n <= 20), and the second line is the P-sequence of a well-formed string. It contains n positive integers, separated with blanks, representing the P-sequence.

Output

The output consists of exactly t lines corresponding to test cases. For each test case, the output line should contain n integers describing the W-sequence of the string corresponding to its given P-sequence.

Sample Input

2
6
4 5 6 6 6 6
9
4 6 6 6 6 8 9 9 9

Sample Output

1 1 1 4 5 6
1 1 2 4 5 1 1 3 9

[java] view plaincopyprint?

1. <p>  
2. </p>import java.io.BufferedInputStream;  
3. import java.util.Scanner;  
4.   
5. public class Main {  
6.   
7.     public static void main(String[] args) throws InterruptedException {  
8.         Scanner sc = new Scanner(System.in);  
9.         int n = sc.nextInt();  
10.         for (int i = 0; i < n; i++) {  
11.             int len = sc.nextInt();  
12.             int P[] = new int[len];// P shows how many left parentheses have been seen since each right parentheses  
13.             int W[] = new int[len];// W shows how many left parentheses have been seen within a pair of parentheses  
14.             // EG:<><>,W=11  
15.             // EG:<<>>,W=12  
16.             // EG:<<<><>>>,W=1134  
17.             char str[] = new char[len * 2];  
18.             int posInP = 0;  
19.             for (int posInStr = 0; posInStr < len; posInStr++) {  
20.                 P[posInStr] = sc.nextInt();  
21.   
22.                 if (posInStr == 0) {// the first P-code  
23.                     for (; posInP < P[posInStr]; posInP++) {  
24.                         str[posInP] = ‘<‘;  
25.                     }  
26.                     str[posInP++] = ‘>‘;  
27.                 } else {  
28.                     if (P[posInStr] > P[posInStr - 1]) {  
29.                         for (int k = 0; k < (P[posInStr] - P[posInStr - 1]); k++) {  
30.                             str[posInP++] = ‘<‘;  
31.                         }  
32.                         str[posInP++] = ‘>‘;  
33.                     } else {// if the next num is the same of the last  
34.                         str[posInP++] = ‘>‘;  
35.                     }  
36.                 }  
37.             }  
38.             // check for W array  
39.             int posInW = 0;  
40.             for (int j = 0; j < len * 2; j++) {  
41.                 if (str[j] == ‘<‘) {  
42.                     continue;  
43.                 }  
44.                 int RightParentheses = 1;  
45.                 for (int j2 = j - 1; j2 >= 0; j2--) {  
46.                     if (str[j2] == ‘>‘) {  
47.                         RightParentheses++;  
48.                     } else {  
49.                         RightParentheses--;  
50.                         W[posInW]++;  
51.                     }  
52.                     if (RightParentheses == 0) {  
53.                         posInW++;  
54.                         break;  
55.                     }  
56.   
57.                 }  
58.             }  
59.             int j;  
60.             for (j = 0; j < len - 1; j++) {  
61.                 System.out.print(W[j] + " ");  
62.             }  
63.             System.out.print(W[j]);  
64.             System.out.println();  
65.         }  
66.     }  
67. }  

PE了好多次，在Eclipse中复制2个testcase，刚复制完就出现第一个的结果，然后按回车就出现另一个结果，本来以为是这个问题，改为把所有的结果收集然后集中输出后又显示RE，最后发现居然是输出的问题，最后一个数字后面不输出空格，这细节真心不是坑爹嘛。。。。

[JAVA][ZOJ 1016][Parencodings]