Задание
В аквариуме есть n пираний с размерами a1, a2, …, an. Пираньи пронумерованы слева направо в том порядке, в котором они живут в аквариуме.
Учёные хотят узнать, есть ли в аквариуме главная пиранья. Пиранья называется главной, если она может съесть всех пираний в аквариуме (за исключением самой себя).
Поскольку аквариум довольно узкий и длинный, пиранья может есть только одну из соседних пираний за один ход. Пиранья может делать сколько угодно ходов. Когда пиранья i съедает какую-либо пиранью, её размер увеличивается на единицу (ai становится равным ai+1).
Ваша задача — найти любую главную пиранью в аквариуме или определить, что таких пираний нет.
Обратите внимание, что вам нужно найти любую (ровно одну) главную пиранью, вам не нужно находить всех подходящих пираний.
Вам нужно ответить на t независимых наборов тестовых данных.
Входные данные
Первая строка теста содержит одно целое число t (1 ≤ t ≤ 2⋅104) — количество наборов тестовых данных. Затем следуют t наборов тестовых данных.
Первая строка набора тестовых данных содержит одно целое число n (2 ≤ n ≤ 3⋅105) — количество пираний в аквариуме. Вторая строка набора тестовых данных содержит n целых чисел a1,a2,…,an (1 ≤ ai ≤ 109), где ai — размер i-й пираньи.
Гарантируется, что сумма всех n не превосходит 3⋅105 (∑n ≤ 3⋅105).
Выходные данные
Для каждого набора тестовых данных выведите ответ на него: -1, если в аквариуме нет главных пираний, или индекс любой главной пираньи. Если существует несколько корректных ответов, вы можете вывести любой.
1
2
3
4
5
6
7