Вам задан массив $$$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.
3 7 4 6 11 11 15 18 20 4 10 10 10 11 3 1 1 1000000000
2 3 6 -1 1 2 3
В первом наборе входных данных невозможно составить невырожденный треугольник со стронами $$$6$$$, $$$11$$$ и $$$18$$$. Обратите внимание, что это не единственный правильный ответ.
Во втором наборе входных данных вы всегда можете составить невырожденный треугольник.
Название |
---|