Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

The problem statement has recently been changed. View the changes.

×
A. Bad Triangle

time limit per test

1 secondmemory limit per test

256 megabytesinput

standard inputoutput

standard outputYou 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.

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.

Example

Input

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

Output

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.

Codeforces (c) Copyright 2010-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Feb/05/2023 01:37:14 (i1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|