12701270 SUSTech Online Judge
Problem 1270 --Magic Number

1270: Magic Number

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 744  Solved: 195
[Submit][Status][Web Board]

Description

There is a queue of n students, indexed from 1 to n from left to right. The height of every student has been given. Because students are standing on one stright line, for every student Ai in the queue, he can only see whom between him and the first student which is taller than him whether he looks left or right. Today teacher wants every student to find two partners, who are the highest one the student can see when he looks left and right respectively. Please help students find their partners. Notice that for every student the partners must shorter than himself.

Input

The first line is integer T (1≤T≤1000), the number of test cases. Each test case consists of two lines. The first line is an integer n (0< n <= 50000) which represents the number of students. The second line lists the heights of students from left to right. It is guaranteed that heights of students are less than 2^31 – 1 and no two students share the same height in one queue.

Output

For each case, print the case number in one line. Then for every student in the testcase, print the index of his two partners in one line seprated by whitespace. If the eligible partner can not be found, the index should be 0. For example, for the student of height 5 in first testcase, he can not see anyone on his left so he can not find left parter and index should be 0. And because he is the highest one in the queue, he can see all the others on his right and the tallest one will be chosen as his right partner. so he choose the student with height 4 and index 3.   

Sample Input

2
5
5 2 4 3 1
5
2 1 4 3 5

Sample Output

Case 1:
0 3
0 0
2 4
0 5
0 0
Case 2:
0 2
0 0
1 4
0 0
3 0

HINT

Source

 

[Submit][Status]