Master of my domain

The following problem recently came up in David Neto's research. It also has applications to politics, especially when you need to find out just how much power you've got.

Consider an array A of n distinct positive integers. We say that position i dominates an interval [j,j'] if

1. , and
2. whenever .

Clearly, for each position i there is a largest interval over which i dominates. Call this the domain of mastery for i. (In fact is the union of all intervals dominated by position i.)

Input: The input to your program is a positive integer d, followed by d data sets. Each data set consists of a positive integer n (with n<500) followed by n distinct natural numbers, A[1] through A[n], each with value at most 10000.

Output: The output for each data set consisting of integer n and array A should be the domain of mastery for each position in A in order from position 1 through n. Each domain of mastery is output by printing the positions of its endpoints, the lower (left-hand) position first. (For instance, a domain of mastery should be printed as follows: 2 7.)

Sample input:

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

Corresponding sample output:

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

Note: For an array A of size n, it is possible to compute all the answers for that array in O(n) time. However, your solution need not be that fast.