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
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 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.)
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.