The ancient mathematician and philosopher Pythagoras believed that reality is mathematical in nature. Present-day biologists study properties of biosequences. A biosequence is a sequence of M integers, which
As an example, consider the biosequence (0,3,5,4,6,2,1,7). The whole biosequence is a framed interval. However, it contains another framed interval (3,5,4,6) and therefore it is not an empodio. The framed interval (3,5,4,6) does not contain a shorter framed interval, so it is an empodio. Furthermore, it is the only empodio in that biosequence.
You are to write a program that, given a biosequence, finds all empodia (plural for empodio) in that biosequence.
There are multiple test cases in the input file which begins with an integer T indicating the total number of test cases.
For each test case, the first line contains a single integer M: the number of integers in the input biosequence. The following M lines contain the integers of the biosequence in the order of the sequence. Each of these M lines contains a single integer. (1<=M<=1100000)
For each test case, the first line of the output is to contain one integer H: the number of empodia in the input biosequence. The following H lines describe all empodia of the input biosequence in the order of appearance of the starting point in the biosequence. Each of these lines is to contain two integers A and B (in that order) separated by a space, where the Ath element of the input biosequence is the first element of the empodio and the Bth element of the input biosequence is the last element of the empodio.
1 8 0 3 5 4 6 2 1 7
1 2 5
Migrated from old NTUJ.
IOI2004
| No. | Testdata Range | Score |
|---|