seuOJ9175 - 坏三角形

题目描述

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

请你找到三个下标 ii、jj、kk，满足 1≤i<j<k≤n1 \le i < j < k \le n，并且无法用 aia_i、aja_j 和 aka_k 作为边长构成一个非退化三角形（即面积不为零的三角形）。例如，边长为 33、44 和 55 可以构成非退化三角形，但边长为 33、44 和 77 则不行。如果不存在这样的三元组，请输出 -1。

输入格式

第一行包含一个整数 tt（1≤t≤10001 \le t \le 1000），表示测试用例的数量。

每个测试用例的第一行包含一个整数 nn（3≤n≤5⋅1043 \le n \le 5 \cdot 10^4），表示数组 aa 的长度。

每个测试用例的第二行包含 nn 个整数 a1,a2,…,ana_1, a_2, \dots, a_n（1≤ai≤1091 \le a_i \le 10^9，ai−1≤aia_{i-1} \le a_i），表示数组 aa。

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

输出格式

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

如果存在一组三元组下标 ii、jj、kk（i<j<ki < j < k），使得无法用 aia_i、aja_j 和 aka_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

解释

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

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