C. Доминирующая пиранья
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В аквариуме есть $$$n$$$ пираний с размерами $$$a_1, a_2, \ldots, a_n$$$. Пираньи пронумерованы слева направо в том порядке, в котором они живут в аквариуме.

Ученые из Берляндского государственного университета хотят узнать, есть ли в аквариуме доминирующая пиранья. Пиранья называется доминирующей, если она может съесть всех пираний в аквариуме (за исключением самой себя, конечно же). Другие пираньи не будут делать ничего, пока доминирующая пиранья будет есть их.

Поскольку аквариум довольно узкий и длинный, пиранья может есть только одну из соседних пираний за один ход. Пиранья может делать сколько угодно ходов (конечно же, до тех пор, пока она может). Более детально:

  • Пиранья $$$i$$$ может съесть пиранью $$$i-1$$$, если пиранья $$$i-1$$$ существует и $$$a_{i - 1} < a_i$$$.
  • Пиранья $$$i$$$ может съесть пиранью $$$i+1$$$, если пиранья $$$i+1$$$ существует и $$$a_{i + 1} < a_i$$$.

Когда пиранья $$$i$$$ съедает какую-либо пиранью, ее размер увеличивается на единицу ($$$a_i$$$ становится равным $$$a_i + 1$$$).

Ваша задача — найти любую доминирующую пиранью в аквариуме или определить, что таких пираний нет.

Обратите внимание, что вам нужно найти любую (ровно одну) доминирующую пиранью, вам не нужно находить всех подходящих пираний.

Например, если $$$a = [5, 3, 4, 4, 5]$$$, то третья пиранья может быть доминирующей. Рассмотрим последовательность ее передвижений:

  • Пиранья съедает вторую пиранью, и $$$a$$$ становится равным $$$[5, \underline{5}, 4, 5]$$$ (подчеркнутая пиранья — наш кандидат).
  • Пиранья съедает третью пиранью, и $$$a$$$ становится равным $$$[5, \underline{6}, 5]$$$.
  • Пиранья съедает первую пиранью, и $$$a$$$ становится равным $$$[\underline{7}, 5]$$$.
  • Пиранья съедает вторую пиранью, и $$$a$$$ становится равным $$$[\underline{8}]$$$.

Вам нужно ответить на $$$t$$$ независимых наборов тестовых данных.

Входные данные

Первая строка теста содержит одно целое число $$$t$$$ ($$$1 \le t \le 2 \cdot 10^4$$$) — количество наборов тестовых данных. Затем следуют $$$t$$$ наборов тестовых данных.

Первая строка набора тестовых данных содержит одно целое число $$$n$$$ ($$$2 \le n \le 3 \cdot 10^5$$$) — количество пираний в аквариуме. Вторая строка набора тестовых данных содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$), где $$$a_i$$$ — размер $$$i$$$-й пираньи.

Гарантируется, что сумма всех $$$n$$$ не превосходит $$$3 \cdot 10^5$$$ ($$$\sum n \le 3 \cdot 10^5$$$).

Выходные данные

Для каждого набора тестовых данных выведите ответ на него: -1, если в аквариуме нет доминирующих пираний, или индекс любой доминирующей пираньи иначе. Если существует несколько корректных ответов, вы можете вывести любой.

Пример
Входные данные
6
5
5 3 4 4 5
3
1 1 1
5
4 4 3 4 4
5
5 5 4 3 2
3
1 1 2
5
5 4 3 5 5
Выходные данные
3
-1
4
3
3
1
Примечание

Первый тестовый набор примера описан в условии задачи.

Во втором тестовом наборе примера нет доминирующей пираньи.

В третьем тестовом наборе примера четвертая пиранья может сначала съесть пиранью слева, и аквариум будет выглядеть как $$$[4, 4, 5, 4]$$$, после этого она сможет съесть любую другую пиранью в аквариуме.