PIPIOJ

Problem A: 区间大师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

HINT

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

[Submit][Status]