Problem1503--区间大师pipi

1503: 区间大师pipi

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 77  Solved: 25
[Submit] [Status] [Web Board] [Creator:]

Description

pipi有一个长度为n的整数数组a_1,a_2,...,a_n,他想让你帮他找出一个区间[l,r]满足1\le l<r\le n使得min(a_l,a_{l+1},...,a_r)*max(a_l,a_{l+1},...,a_r)最小。

Input

输入包含t组测试用例,第一行一个整数t(1\le t\le 200000)
每组测试用例第一行一个整数n(2\le n\le 200000)
每组测试用例第二行n个整数a_1,a_2,...,a_n(1\le a_i\le 10^9)
输入保证所有n之和不超过200000

Output

输出t行,第i行两个整数l\ r表示第i组测试用例的答案,如果有多个答案,输出区间长度最短的,如果仍然有多个,输出l最大的。

Sample Input

11
5
1 2 1 1 1
4
6 7 7 1
4
5 1 7 9
5
8 5 3 6 7
8
8 9 4 9 3 1 2 7
7
5 4 6 7 1 10 2
7
10 3 2 3 8 9 1
7
10 10 9 9 5 8 3
8
3 10 7 1 7 2 9 9
6
2 9 5 9 7 3
7
5 4 2 5 10 10 9

Sample Output

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

HINT

第一组测试数据中,min(a_4,a_5)*max(a_4,a_5)=1,达到最小。

Source/Category

简单