#P1398A. Bad Triangle
-
ID: 5517
Type: RemoteJudge
1000ms
256MiB
Tried: 0
Accepted: 0
Difficulty: (None)
Uploaded By:
Hydro
Tags> Bad Triangle
No submission language available for this problem.
Description
You are given an array $a_1, a_2, \dots , a_n$, which is sorted in non-decreasing order ($a_i \le a_{i + 1})$.
Find three indices $i$, $j$, $k$ such that $1 \le i < j < k \le n$ and it is impossible to construct a non-degenerate triangle (a triangle with nonzero area) having sides equal to $a_i$, $a_j$ and $a_k$ (for example it is possible to construct a non-degenerate triangle with sides $3$, $4$ and $5$ but impossible with sides $3$, $4$ and $7$). If it is impossible to find such triple, report it.
The first line contains one integer $t$ ($1 \le t \le 1000$) — the number of test cases.
The first line of each test case contains one integer $n$ ($3 \le n \le 5 \cdot 10^4$) — the length of the array $a$.
The second line of each test case contains $n$ integers $a_1, a_2, \dots , a_n$ ($1 \le a_i \le 10^9$; $a_{i - 1} \le a_i$) — the array $a$.
It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$.
For each test case print the answer to it in one line.
If there is a triple of indices $i$, $j$, $k$ ($i < j < k$) such that it is impossible to construct a non-degenerate triangle having sides equal to $a_i$, $a_j$ and $a_k$, print that three indices in ascending order. If there are multiple answers, print any of them.
Otherwise, print -1.
Input
The first line contains one integer $t$ ($1 \le t \le 1000$) — the number of test cases.
The first line of each test case contains one integer $n$ ($3 \le n \le 5 \cdot 10^4$) — the length of the array $a$.
The second line of each test case contains $n$ integers $a_1, a_2, \dots , a_n$ ($1 \le a_i \le 10^9$; $a_{i - 1} \le a_i$) — the array $a$.
It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$.
Output
For each test case print the answer to it in one line.
If there is a triple of indices $i$, $j$, $k$ ($i < j < k$) such that it is impossible to construct a non-degenerate triangle having sides equal to $a_i$, $a_j$ and $a_k$, print that three indices in ascending order. If there are multiple answers, print any of them.
Otherwise, print -1.
Samples
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
Note
In the first test case it is impossible with sides $6$, $11$ and $18$. Note, that this is not the only correct answer.
In the second test case you always can construct a non-degenerate triangle.