В аквариуме есть \(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\) независимых наборов тестовых данных.
Выходные данные
Для каждого набора тестовых данных выведите ответ на него: -1, если в аквариуме нет доминирующих пираний, или индекс любой доминирующей пираньи иначе. Если существует несколько корректных ответов, вы можете вывести любой.
Примечание
Первый тестовый набор примера описан в условии задачи.
Во втором тестовом наборе примера нет доминирующей пираньи.
В третьем тестовом наборе примера четвертая пиранья может сначала съесть пиранью слева, и аквариум будет выглядеть как \([4, 4, 5, 4]\), после этого она сможет съесть любую другую пиранью в аквариуме.