Problem 1270 --Magic Number
1270: Magic NumberTime Limit: 1 Sec Memory Limit: 128 MB
Submit: 742 Solved: 194
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.
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.
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.
5 2 4 3 1
2 1 4 3 5