← 返回题目列表

Codeforces · 1398/A

A. 坏三角形

中文机器翻译题面 查看原题

给定一个数组 $$$a_1, a_2, \dots , a_n$$$,该数组按非降序排序 ($$$a_i \le a_{i + 1})$$$。

找到三个索引 $$$i$$$、$$$j$$$、$$$k$$$ 使得 $$$1 \le i < j < k \le n$$$ 且不可能构造边长等于 $$$a_i$$$、$$$a_j$$$ 和 $$$a_k$$$ 的非退化三角形(面积非零的三角形)(例如,可以构造一个边为 $$$3$$$、$$$4$$$ 和 $$$5$$$ 的非退化三角形,但不可能构造边为 $$$3$$$、$$$4$$$ 和 $$$7$$$ 的非退化三角形。如果不可能找到这样的三元组,请报告。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 1000$$$) — 测试用例的数量。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$3 \le n \le 5 \cdot 10^4$$$) — 数组 $$$a$$$ 的长度。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots , a_n$$$ ($$$1 \le a_i \le 10^9$$$; $$$a_{i - 1} \le a_i$$$) - 数组 $$$a$$$。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$10^5$$$。

输出

对于每个测试用例,将其答案打印在一行中。

如果存在三个索引 $$$i$$$、$$$j$$$、$$$k$$$ ($$$i < j < k$$$),因此不可能构造边等于 $$$a_i$$$、$$$a_j$$$ 和 $$$a_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

注意

在第一个测试用例中,边 $$$6$$$、$$$11$$$ 和 $$$18$$$ 是不可能的。请注意,这不是唯一的正确答案。

在第二个测试用例中,您始终可以构造一个非退化三角形。