DRUIDEOI  Fata7y Ya Warda!
Druid (AKA Amr Alaa ElDeen) and little EOIers have finished their training and they are playing "Fatta7y ya warda!". It's a kids game when everyone holds hands with two other kids forming a circle, and they keep saying "Fatta7y ya warda!" (Flourish, flower!) (moving away from each other, while still holding hands, to form a huge circle), then "2affely ya warda!" (Die, flower!) (moving back as close to each other as possible, while still holding hands, to form a tiny circle, i.e. a point). That's it!
Anyway the point is...
While Eagle (AKA Mohamed Ahmed) was watching them playing he was wondering, who's the first person taller than Druid on his left? Similarly, who's the first person taller than Druid on his right? Help Eagle find the answer for each person not just Druid.
Input
The input starts with an integer T (1 ≤ T ≤ 20), the number of test cases.
Each test case contains two lines. The first line contains a single integer N (1 ≤ N ≤ 10^{5}), the number of persons playing the game. The second line contains N integers h_{i} (1 ≤ h_{i} ≤ 10^{9}) the height of the ith person. They are numbered 1 to N starting from Druid.
Output
For each test case print N lines, in the ith line print 2 numbers, the index of the first person taller than the ith person on his left, and the index of the first person taller than the ith person on his right. If no one is taller than the ith person print 1 1.
Example
Input:
3 5
172 170 168 171 169
3
172 169 172
1
172
Output: 1 1
1 4
2 4
1 1
4 1
1 1
1 3
1 1
1 1
Note
hide comments
:.Mohib.::
20160121 07:08:12
Nice one..!!


Baojun Wang:
20151019 22:19:17
brute force passed 

snehil10111995:
20150810 15:09:00
my solution gives tle. Any hint? 

Akash Goel:
20150713 15:21:39
use scanf printf in c++. 

Akhilesh Anandh:
20150708 08:17:34
nice problem! 

Naveen Kumar Shukla:
20150704 13:47:12
Finally accepted....nice question. Feeling great!! 

Marko Puza:
20150630 15:16:02
I can by no means find out what is wrong with my solution.


Pranye Mawai:
20150627 14:57:55
o(n) possible.. nice ques.. 

gamer496:
20150625 16:06:53
Good one 

Soma:
20150624 08:14:47
@anyone : can there be two or more persons with same height?

Added by:  eagle93 
Date:  20150620 
Time limit:  2s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 JSMONKEY 