F. 坏三角形

传统 1000 ms 256 MiB
标准 IO
Special Judge

题目描述

给定一个按非递减顺序排序的数组 a1,a2,,ana_1, a_2, \dots, a_n(即 aiai+1a_i \le a_{i+1})。

请你找到三个下标 iijjkk,满足 1i<j<kn1 \le i < j < k \le n,并且无法用 aia_iaja_jaka_k 作为边长构成一个非退化三角形(即面积不为零的三角形)。例如,边长为 334455 可以构成非退化三角形,但边长为 334477 则不行。如果不存在这样的三元组,请输出 -1。

输入格式

第一行包含一个整数 tt1t10001 \le t \le 1000),表示测试用例的数量。

每个测试用例的第一行包含一个整数 nn3n51043 \le n \le 5 \cdot 10^4),表示数组 aa 的长度。

每个测试用例的第二行包含 nn 个整数 a1,a2,,ana_1, a_2, \dots, a_n1ai1091 \le a_i \le 10^9ai1aia_{i-1} \le a_i),表示数组 aa

保证所有测试用例中 nn 的总和不超过 10510^5

输出格式

对于每个测试用例,输出一行答案。

如果存在一组三元组下标 iijjkki<j<ki < j < k),使得无法用 aia_iaja_jaka_k 构成非退化三角形,输出这三个下标,按升序排列。如果有多组答案,输出任意一组即可。

如果不存在这样的三元组,输出 -1。

样例

输入 #1

3
7
4 6 11 11 15 18 20
4
10 10 10 11
3
1 1 1000000000

输出 #1

2 3 6
-1
1 2 3

解释

在第一个测试用例中,边长为 6611111818 时无法构成非退化三角形。注意,这并不是唯一的正确答案。

在第二个测试用例中,总是可以构成非退化三角形。